首页 > 代码库 > NOIP2016 组合数问题

NOIP2016 组合数问题

杨辉三角前缀和

 1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4  5 int t,k,n,m; 6 int C[2005][2005],S[2005][2005]; 7  8 int read() 9 {10     int x=0,f=1;char ch=getchar();11     while(ch<0||ch>9){if(ch==-)f=-f;ch=getchar();}12     while(ch>=0&&ch<=9){x=x*10+ch-0;ch=getchar();}13     return x*f;14 }15 16 void init()17 {18     C[0][0]=1;19     for(int i=1;i<=2000;i++) C[i][0]=C[i][i]=1;20     for(int i=2;i<=2000;i++)21         for(int j=1;j<=2000;j++)22         {23             C[i][j]=(C[i-1][j-1]+C[i-1][j])%k;24             S[i][j]=S[i-1][j]+S[i][j-1]-S[i-1][j-1];25             if(j<=i&&C[i][j]==0) S[i][j]++;26         }27 }28 29 int main()30 {31     t=read();k=read();32     init();33     while(t--)34     {35         n=read();m=read();36         cout<<S[n][m]<<endl;37     }38     return 0;39 }

 

NOIP2016 组合数问题