洛谷P2822 组合数问题
P2822 组合数问题
题目描述
有多少C(i,j)是k的倍数
输入输出格式
输入格式:
第一行有两个整数 t,k 其中 tt 代表该测试点总共有多少组测试数据,k的意义见问题描述。
接下来 t 行每行两个整数 n,m,其中 n,m的意义见问题描述。
输入输出样例
输入样例#1:
1 2
3 3
输出样例#1:
1
输入样例#2:
2 5
4 5
6 7
输出样例#2:
0
7
【子任务】
分析:求模k意义下的杨辉三角形,前缀和统计个数即可。
代码
#include <cstdio>
#define N 2005
using namespace std;
int c[N][N],sum[N][N];
int n,m;
int main()
{
int T,k;
scanf("%d%d", &T, &k);
c[0][0] = c[1][0] = c[1][1] = 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] + c[i - 1][j - 1]) % k;
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
if (!c[i][j]) sum[i][j]++;
}
sum[i][i + 1] = sum[i][i];
}
while (T--)
{
scanf("%d%d", &n, &m);
if (n < m) printf("%d\n", sum[n][n]);
else printf("%d\n", sum[n][m]);
}
}