https://www.luogu.com.cn/problem/P2822
由于是从c[n][m]从寻找是K的倍数的nm值，而且是多组测试实例，所以使用杨辉三角打表便于查询
C(n,m)=C(n-1,m-1)+C(n-1,m)
而在查询个数的时候，因为存在记录符合条件的nm值的个数，所以这个记录可以使用前缀和的形式记录来节省时间。
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
#include<iostream> using namespace std; long long c[2020][2020], dp[2020][2020]; int t, k; void build() { c[0][0] = c[1][1] = c[1][0] = 1; for (int i = 2; i <= 2000; i++) { c[i][0] = 1; for (int j = 1; j <= i; j++) { c[i][j] = (c[i - 1][j - 1] + c[i - 1][j])%k; dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]; if (!c[i][j])dp[i][j]++;//如果上面c[i][j]取余的话结果为0，这里在dp[i][j]个数就要加1 } dp[i][i + 1] = dp[i][i]; } } int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); cin >> t >> k; build(); for (int i = 0; i < t; i++) { int n, m; cin >> n >> m; if(m>n)cout << dp[n][n] << endl; else cout << dp[n][m] << endl; } }
原文：https://www.cnblogs.com/Jason66661010/p/12863510.html