首页 > 代码库 > 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 组合数问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。