记录编号	607461	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	2559.[NOIP 2016]组合数问题	最终得分	100
用户昵称	hsl_beat	是否通过	通过
代码语言	C++	运行时间	1.322 s
提交时间	2025-10-16 19:39:47	内存使用	47.92 MiB

#include<bits/stdc++.h>
#define int long long 
using namespace std;
int c[2010][2010], ans[2010][2010];
signed main()
{
    freopen("problem.in", "r", stdin);
    freopen("problem.out", "w", stdout);
    int T, k;
    cin >> T >> k; 
    for (int i = 0; i <= 2000; i++) {
        c[i][0] = c[i][i] = 1;
        for (int j = 1; j <= i; j++) {
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % k;
        }
    }
    for (int i = 0; i <= 2000; i++) {
        int cnt = 0;
        for (int j = 1; j <= i; j++)  {
            cnt += (c[i][j] == 0);
            if (i == j) {
                ans[i][j] = ans[i - 1][j - 1] + cnt;
            } else {
                ans[i][j] = ans[i - 1][j] + cnt;
            }
        }
    }
    while (T--) {
        int n, m;
        cin >> n >> m;
        m = min(n, m);
        cout << ans[n][m] << '\n';
    }
    return 0;
}