组合数问题

P2822 [NOIP2016 提高组] 组合数问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

• dp数组求杨辉三角模k后的取值，ans数组为二维前缀和，记录答案，可降低查询复杂度
• 杨辉：dp[i][j]=dp[i-1][j]+dp[i-1][j-1]二维前缀和：ans[i][j]=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1](上加左减左上）

#include <bits/stdc++.h>
using namespace std;
#define N 1e5
#define INF 2e9
#define MAX 10000
// https://www.luogu.com.cn/problem/P2822
int n, k;
int dp[MAX][MAX], ans[MAX][MAX];
void cal()
{
    dp[0][0] = 1;
    dp[1][0] = dp[1][1] = 1;
    for (int i = 2; i <= 2000; i++)
    {
        dp[i][0] = 1;
        for (int j = 1; j <= i; j++)
        {
            dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % k;
            ans[i][j] = ans[i - 1][j] + ans[i][j - 1] - ans[i - 1][j - 1];
            if (!dp[i][j])
                ans[i][j]++;
        }
        ans[i][i + 1] = ans[i][i];
    }
}
int m, t;
int main()
{
    cin >> t >> k;
    cal();
    while (t--)
    {
        scanf("%d%d", &n, &m);
        m = min(m, n);
        printf("%d\n", ans[n][m]);
    }
}