回忆京都(Memories of Kyoto) 题解

思路分析

由于询问次数 $q \le 10^4$，不能每次询问都 $O(nm)$ 求和。先利用杨辉三角递推 $\mathrm{C}_j^i = (\mathrm{C}_{j-1}^{i-1} + \mathrm{C}_{j-1}^i) \bmod 19260817$ 预处理出 $0 \le i, j \le 1000$ 的所有组合数（$i > j$ 处为 $0$），再对二维矩阵 $A[i][j] = \mathrm{C}_j^i$（$1 \le i, j \le 1000$）求二维前缀和 S[i][j]。随后每次询问直接 $O(1)$ 输出 S[n][m]（当 $n = 0$ 或 $m = 0$ 时 S[n][m] = 0）。总时间复杂度 $O(N^2 + q)$。

参考代码

#include <iostream>
using namespace std;

const int MOD = 19260817;
const int MX = 1005;
int C[MX][MX];
int S[MX][MX];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for (int j = 0; j <= 1000; ++j)
    {
        C[j][0] = 1;
        for (int i = 1; i <= j; ++i)
            C[j][i] = (C[j - 1][i - 1] + C[j - 1][i]) % MOD;
    }
    for (int i = 1; i <= 1000; ++i)
    {
        for (int j = 1; j <= 1000; ++j)
        {
            long long val = 1LL * S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + C[j][i];
            val %= MOD;
            if (val < 0) val += MOD;
            S[i][j] = (int)val;
        }
    }
    int q;
    if (!(cin >> q)) return 0;
    while (q--)
    {
        int n, m;
        cin >> n >> m;
        cout << S[n][m] << "\n";
    }
    return 0;
}