AcWing 523. 组合数问题
原题链接
简单
作者:
普通朋友
,
2023-02-10 12:20:51
,
所有人可见
,
阅读 153
#include<bits/stdc++.h>
using namespace std;
const int N=2010;
int c[N][N];
int s[N][N];
int t,k;
int main()
{
scanf("%d%d", &t, &k);
for(int i=0;i<N;i++)
{
for(int j=0;j<=i;j++)
{
if(!j)c[i][j]=1%k;
else c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;
if(!c[i][j])s[i][j]=1;
}
}
for(int i=1;i<N;i++)
{
for(int j=1;j<N;j++)
s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];//原来是s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]
}//这里直接用s[i][j]进行操作,因为这里的a[i][j]和s[i][j]是一样的,如果能整除就是1
//注意边界
//从0开始,但是要判断i,j分别情况,再进行相加
while(t--)
{
int n,m;
scanf("%d%d",&n,&m);
printf("%d\n",s[n][m]);
}
return 0;
}