【NOIP2016】组合数问题

题面

分析

那个公式就是骗你的。然而是个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的倍数

有一个特判

代码

  1. /*关于特判 
  2. 我们存的杨辉三角长这样 
  3. 1 
  4. 1 1 
  5. 1 2 1 
  6. 1 3 3  1 
  7. 1 4 6  4  1 
  8. 1 5 10 10 5  1  
  9. 1 6 15 20 15 6 1  
  10. 比如到第四行第四个位置,选ans[i-1][j]会加入第三行第四个位置的答案 
  11. 但这个位置为0,显然不对。 
  12. 因为本来上一行也只有三个元素。  
  13. 所以 应该选择ans[i-1][j-1],访问第三行第三个位置并计入答案  
  14. */   
  15.   
  16. #include<bits/stdc++.h>  
  17. using namespace std;  
  18. #define N 2020  
  19. #define ll long long  
  20. ll t,n,m,k,cnt,tmp,now;  
  21. ll h[N],c[N][N],ans[N][N];  
  22. int main()  
  23. {  
  24.     scanf("%lld%lld",&t,&k);  
  25.     c[0][0]=1;   
  26.     for(int i=1;i<N;i++)  
  27.     {  
  28.         c[i][0]=1;  
  29.         for(int j=1;j<=i;j++)  
  30.         {  
  31.             c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;  
  32.             if(c[i][j]==0)h[i]++;  
  33.             ans[i][j]=ans[i-1][j]+h[i];  
  34.             if(i==j)ans[i][j]=ans[i-1][j-1]+h[i];  
  35.         }         
  36.     }  
  37.     while(t--)  
  38.     {  
  39.         scanf("%lld%lld",&n,&m);  
  40.         printf("%lld ",ans[n][min(n,m)]);  
  41.     }  
  42. }   
原文地址:https://www.cnblogs.com/NSD-email0820/p/9829341.html