题面
分析
那个公式就是骗你的。然而是个OIer都会知道另一个递推公式C(N,M)=C(N-1，M-1)+C(N-1，M)
可以理解为在N个中选M个，要选第N个就是在剩下N-1个中选M-1个，不选第N个就是在N-1个中选M个
然后暴力取模k,90分就到手了，胡思乱想反而容易挂，比如我。
最后用二维前缀和维护一下答案，h[i]表示第i行到目前为止有多少是k的倍数
有一个特判
代码
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- #include<bits/stdc++.h>
- using namespace std;
- #define N 2020
- #define ll long long
- ll t,n,m,k,cnt,tmp,now;
- ll h[N],c[N][N],ans[N][N];
- int main()
- {
- scanf("%lld%lld",&t,&k);
- c[0][0]=1;
- for(int i=1;i<N;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;
- if(c[i][j]==0)h[i]++;
- ans[i][j]=ans[i-1][j]+h[i];
- if(i==j)ans[i][j]=ans[i-1][j-1]+h[i];
- }
- }
- while(t--)
- {
- scanf("%lld%lld",&n,&m);
- printf("%lld\n",ans[n][min(n,m)]);
- }
- }
【NOIP2016】组合数问题
原文：https://www.cnblogs.com/NSD-email0820/p/9829341.html
