You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

5.1 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

##AcWing 1315. 网格

一、题目描述

某城市的街道呈网格状,左下角坐标为 A(0,0),右上角坐标为 B(n,m),其中 n≥m

现在从 A(0,0)点 出发,只能沿着街道向 正右方 或者 正上方 行走,且不能经过图示中直线左上方的点,即任何途径的点 (x,y) 都要满足 x≥y,请问在这些前提下,到达 B(n,m) 有多少种走法。

输入格式

仅有一行,包含两个整数 nm,表示城市街区的规模。

输出格式

输出一个整数,表示不同的方案总数。

数据范围 1≤m≤n≤5000

输入样例:

6 6

输出样例:

132

二、解题思路

用求卡特兰数的方法分析一下这个题目就可以得到答案,关于卡特兰数的分析:网址

我们需要求出点 (n, m) 关于y = x + 1对称的点的坐标,假设为(a, b),则任何一种不合法的方案都可以转化为到达(a, b)的路径,如下图:

则答案为:\large \displaystyle C_{m+n}^n-C_{m+n}^a,问题就转变为了如何求解坐标(a, b)

解析几何法

这是高中知识,我们可以列方程求解,根据垂直可以得到一个等式,根据线段中点在对称轴上可以得到另一个等式,可以得到:


\large \left\{\begin{matrix}
1 \times \frac{b-m}{a-n}=-1 & 解释:两条直线垂直,则斜率乘积为-1 \\ 
y=x+1 \rightarrow \frac{b+m}{2}=\frac{a+n}{2}+1 & 解释:中点公式 \\
\end{matrix}\right.

解方程可得a=m-1,b=n+1,因此答案为

\large \displaystyle C_{m+n}^n-C_{m+n}^{m-1}

平移对称轴法

  • ① 将直线y=x+1、点(n,m)全部向下移动一个单位,就变成了一条直线y=x和点(n,m-1)
  • ② 求(n,m-1)关于直线y=x的对称点就是(m-1,n)
  • ③ 再将直线和点全部上移回去,就得到(m-1,n+1)

因此,答案也是: \large \displaystyle C_{m+n}^n-C_{m+n}^{m-1}

  1. 上面两种方法使用其中一种即可。
  2. 本题需要使用到高精度求解,如果递推的话计算量为10000^2=1×10^8,再加上高精度计算会超时,因此这里求解阶乘的方式然后带入公式求组合数,类似于AcWing 888. 求组合数 IV

三、实现代码

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;
int a[N], b[N]; // 两个整数数组保存高精度计算的结果

// 欧拉筛
int primes[N], cnt;
bool st[N];
void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] * i <= n; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

// 计算n中包含质数p的个数
int get(int n, int p) {
    int s = 0;
    while (n) s += n / p, n /= p;
    return s;
}

// 高精乘低精
void mul(int a[], int &al, int b) {
    int t = 0;
    for (int i = 1; i <= al; i++) {
        t += a[i] * b;
        a[i] = t % 10;
        t /= 10;
    }
    while (t) {
        a[++al] = t % 10;
        t /= 10;
    }
}

// 高精减高精
void sub(int a[], int &al, int b[]) {
    for (int i = 1, t = 0; i <= al; i++) {
        a[i] -= t + b[i];
        if (a[i] < 0)
            a[i] += 10, t = 1;
        else
            t = 0;
    }
    while (al > 1 && !a[al]) al--;
}

// C(a,b)的结果高精度保存到c数组同时返回c数组的长度len
void C(int a, int b, int c[], int &cl) {
    // 高精度的基底乘法的基数是1
    c[1] = 1;
    cl = 1; // 由于高精度数组中只有一位是1所以长度也是1

    for (int i = 0; i < cnt; i++) { // 枚举区间内所有质数
        int p = primes[i];
        /*
        C(a,b)=a!/(b! * (a-b)!)
        a!中有多少个质数因子p
        减去(a-b)!的多少个质数因子p,
        再减去b!的质数因子p的个数就是总个数
        s记录了p这个质数因子出现的次数
        */
        int s = get(a, p) - get(b, p) - get(a - b, p);
        while (s--) mul(c, cl, p); // 不断的乘p,结果保存到数组c中。len将带回c的有效长度
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    // 筛质数
    get_primes(2 * n);
    int al, bl;
    C(n + m, m, a, al);     // C(n+m,m)将高精度结果记录到a数组中,返回数组有效长度al
    C(n + m, m - 1, b, bl); // C(n+m,m-1)将高精度结果记录到b数组中

    sub(a, al, b); // 计算a-b的高精度减法
    
    // 输出结果,注意是倒序
    for (int i = al; i; i--) printf("%d", a[i]);
    return 0;
}