用了组合数的性质和前缀和，但是只能过前面两个，后面再试试……
题目
组合数问题
时间限制: 1.0s 内存限制: 256.0MB 本题总分：25 分
【问题描述】
给 n, m, k，求有多少对 (i, j) 满足 1 ≤ i ≤ n, 0 ≤ j ≤ min(i, m) 且 C(i,j) ≡
0(mod k)，k 是质数。其中 C(i,j)是组合数，表示从 i 个不同的数中选出 j 个组成
一个集合的方案数。
【输入格式】
第一行两个数 t, k，其中 t 代表该测试点包含 t 组询问，k 的意思与上文中 相同。
接下来 t 行每行两个整数 n, m，表示一组询问。
【输出格式】
输出 t 行，每行一个整数表示对应的答案。由于答案可能很大，请输出答 案除以 109 + 7 的余数。
【样例输入】
1 2
3 3
【样例输出】
1
【样例说明】
在所有可能的情况中，只有 C(2,1)= 2 是 2 的倍数。
【样例输入】
2 5
4 5
6 7
【样例输出】
0
7
【样例输入】
3 23
23333333 23333333
233333333 233333333
2333333333 2333333333
【样例输出】
851883128
959557926
680723120
【数据规模和约定】
对于所有评测用例，1 ≤ k ≤ 10^8, 1 ≤ t ≤ 10^5, 1 ≤ n, m ≤ 10^18，且 k 是质数。 评测时将使用 10 个评测用例测试你的程序，每个评测用例的限制如下：
|
评测用例编号 |
t |
n, m |
k |
|
1, 2 |
≤ 1 |
≤ 2000 |
≤ 100 |
|
3, 4 |
≤ 10^5 |
≤ 2000 |
≤ 100 |
|
5, 6, 7 |
≤ 100 |
≤ 10^18 |
≤ 100 |
|
8, 9, 10 |
≤ 10^5 |
≤ 10^18 |
≤ 10^8 |
代码
1 #include<iostream> 2 #include<cmath> 3 #define ll long long 4 #define mod (long long)(1e9+7) 5 using namespace std; 6 ll c[2005][2005]; 7 ll s[2005][2005]; 8 void init(ll k){//依据组合数的性质产生杨辉三角图，并产生前缀和 9 c[0][0]=1; 10 for(int i=1;i<2001;i++){ 11 c[i][0]=1; 12 c[i][i]=1; 13 for(int j=1;j<i;j++){ 14 c[i][j]=(c[i-1][j-1]%k+c[i-1][j]%k)%k;//组合数的性质 15 if(!c[i][j]) s[i][j]=1; 16 s[i][j]=(s[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1])%mod; 17 } 18 s[i][i]=s[i][i-1]; 19 } 20 } 21 int main(){ 22 ll t,k; 23 cin>>t>>k; 24 ll n,m; 25 init(k); 26 while(t--){ 27 cin>>n>>m; 28 cout<<s[n][min(n,m)]; 29 } 30 31 32 }