网格-不用写高精度减法的解法

通过一些数学推导可以避免使用高精度减法。

得到组合公式的表达式的步骤和889. 满足条件的01序列相同，这里简单地写一下数学推导。

首先求$(n, m)$相对于直线$y = x + 1$的对称点$(a, b)$，
$$ \frac{m + b}{2} = \frac{n + a}{2}, \\ \frac{b - m}{a - n} \cdot 1 = -1, $$

可以解得，
$$ a = m - 1, \\ b = n + 1 $$

最终答案应该为$C_{m + n}^n - C_{m + n}^{m - 1}$，
这里可以进一步化简，
$$ \begin{aligned} C_{m + n}^n - C_{m + n}^{m - 1} &= \cfrac{(m + n)!}{n!m!} - \cfrac{(m+n)!}{(m - 1)!(n + 1)!} \\ &= (m + n)!\cfrac{n + 1 - m}{(n + 1)!m!} \\ &= \cfrac{(m + n)!}{(n + 1)!m!}(n - m + 1) \end{aligned} $$

这样化简之后，就只有高精度乘法需要写了。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <bitset>
#include <vector>

using std::cin, std::cout;
using std::bitset, std::vector;
using LL = long long;

const int N = 1e4 + 10;

bitset<N> st;
int prime[N], cnt;

void sieve(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!st[i]) prime[cnt++] = i;
        for (int j = 0; prime[j] * i <= n; j++)
        {
            st[prime[j] * i] = true;
            if (i % prime[j] == 0) break;
        }
    }
}

int Legendre(int n, int p)
{
    int cnt = 0;
    while (n)
    {
        cnt += n / p;
        n /= p;
    }
    return cnt;
}

vector<int> mul(vector<int>& A, int b)
{
    vector<int> C;
    int t = 0;
    for (int a : A)
    {
        t += a * b;
        C.push_back(t % 10);
        t /= 10;
    }
    while (t)
    {
        C.push_back(t % 10);
        t /= 10;
    }
    return C;
}

void show(vector<int>& A)
{
    for (int i = A.size() - 1; i >= 0; i--) cout << A[i];
    cout << '\n';
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int n, m; cin >> n >> m;
    sieve(n + m);

    vector<int> res;
    res.push_back(1);

    for (int i = 0; i < cnt; i++)
    {
        int p = prime[i];
        int c = Legendre(m + n, p) - Legendre(n + 1, p) - Legendre(m, p);
        while (c--) res = mul(res, p);
    }
    res = mul(res, n - m + 1);

    show(res);

    return 0;
}