【题意】 小葱想知道如果给定
n,m,k
，对于所有的
0<=i<=n,0<=j<=min(i,m)
有多少对
C(i,j)
满足是
k
<script type="math/tex" id="MathJax-Element-38">k</script>的倍数。
题解：
想当年我不会做，现在想看看会不会。直接暴力预处理出每个C%k的余数就好了……再求一下前缀和……当时的我竟然不会做……现在十几分钟就AC了……
代码：
#include<cstdio>
#include<cstring>
const int maxn=
2010;
int t,k,n,m,C[maxn][maxn],sum[maxn][maxn];
void work()
{
C[
0][
0]=
1;
for(
int i=
1;i<=
2000;i++)C[i][
0]=
1;
for(
int i=
1;i<=
2000;i++)
for(
int j=
1;j<=i;j++)
C[i][j]=(C[i-
1][j]+C[i-
1][j-
1])%k;
for(
int j=
1;j<=
2000;j++)
{
sum[j-
1][j]=
0;
for(
int i=j;i<=
2000;i++)
{
sum[i][j]=sum[i-
1][j];
if(C[i][j]==
0)sum[i][j]++;
}
}
}
int main()
{
scanf(
"%d%d",&t,&k);
work();
while(t--)
{
int ans=
0;
scanf(
"%d%d",&n,&m);
for(
int j=
0;j<=m;j++)
ans+=sum[n][j];
printf(
"%d\n",ans);
}
}
