题目描述
组合数C(n,m)表示的是从 n个物品中选出 m个物品的方案数。举个例子，从(1, 2, 3)三个物品中选择两个物品可以有(1, 2),(1, 3),(2, 3)这三种选择方法。根据组合数的定义，我们可以给出计算组合数C(n,m)的一般公式：
C(n,m)=n!/(m!(n-m)!)
其中 n!= 1×2×···× n 。
小葱想知道如果给定 n, m和 k，对于所有的0≤ i≤ n,0≤ j≤min( i, m)有多少对
|
( i, j)满足C(i,j)是 k的倍数。
输入
第一行有两个整数 t, k，其中 t代表该测试点总共有多少组测试数据， k的意义见【问题描述】。
接下来 t行每行两个整数 n, m，其中 n, m的意义见【问题描述】。
输出
t行，每行一个整数代表所有的0≤ i≤ n,0≤ j≤min( i, m)中有多少对( i, j)满足C(i,j)是 k的倍数。
样例输入
1 2 3 3 2 5 4 5 6 7
样例输出
1 0 7
提示
【样例 1 说明】
在所有可能的情况中，只有C(2,1)=2 是2的倍数。
| 测试点 | n | m | k | t |
| 1 | ≤3 | ≤3 | =2 | =1 |
| 2 | =3 | ≤104 | ||
| 3 | ≤7 | ≤7 | =4 | =1 |
| 4 | =5 | ≤104 | ||
| 5 | ≤10 | ≤10 | =6 | =1 |
| 6 | =7 | ≤104 | ||
| 7 | ≤20 | ≤100 | =8 | =1 |
| 8 | =9 | ≤104 | ||
| 9 | ≤25 | ≤2000 | =10 | =1 |
| 10 | =11 | ≤104 | ||
| 11 | ≤60 | ≤20 | =12 | =1 |
| 12 | =13 | ≤104 | ||
| 13 | ≤100 | ≤25 | =14 | =1 |
| 14 | =15 | ≤104 | ||
| 15 | ≤60 | =16 | =1 | |
| 16 | =17 | ≤104 | ||
| 17 | ≤2000 | ≤100 | =18 | =1 |
| 18 | =19 | ≤104 | ||
| 19 | ≤2000 | =20 | =1 | |
| 20 | =21 | ≤104 |
题解
这道题刚看到以为要分解质因数，后来想到用C(i,j)=C(i-1,j-1)+C(i-1,j)就可以了
用c[i][j]表示C(i,j)%k的值，再用s[i][j]表示第i行c[i][j]的前缀和，再判断当前的c[i][j]是否等于0，如果c[i][j]等于0那么s[i][j]++
每次输入的时候把前i个s[i][min(i,m)]加起来就可以了
因为n<=2000,t<=10000,所以枚举一遍i不会超
总的来说应该比较好理解的
#include#define N 2005using namespace std;int T,k,n,m,ans;int c[N][N],s[N][N];int main(){ scanf("%d%d",&T,&k); c[0][0]=1; for (int i=1;i<=N-5;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; } for (int i=1;i<=N-5;i++){ if (!c[i][1]) s[i][1]++; for (int j=2;j<=i;j++){ s[i][j]=s[i][j-1]; if (!c[i][j]) s[i][j]++; } } while (T--){ ans=0; scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) ans=ans+s[i][min(i,m)]; printf("%d\n",ans); } return 0;}