【NOIP 2016 提高组】†组合数问题

2019-04-14 19:44发布

站内文章 / 模拟电子
16167 0 1737
class="markdown_views prism-atom-one-light">

Description

这里写图片描述

Solution

第一反应是分解质因数，
后来发现直接做杨辉三角形+模即可， 复杂度：O(n2)

Code

#include #include #include #define fo(i,a,b) for(int i=a;i<=b;i++) using namespace std; typedef long long LL; const int N=2005; int n,m,K; int f[N][N],g[N][N]; int sum[N][N]; int main() { freopen("problem.in","r",stdin); freopen("problem.out","w",stdout); int q,w,_; scanf("%d%d",&_,&K); fo(i,0,2000) { g[i][0]=g[i][i]=1; fo(j,1,i-1) { g[i][j]=(g[i-1][j]+g[i-1][j-1])%K; if(!g[i][j])f[i][j]++; } } fo(i,1,2000) fo(j,1,2000)f[i][j]+=f[i-1][j]+f[i][j-1]-f[i-1][j-1]; while(_--) { scanf("%d%d",&n,&m);m=min(n-1,m); printf("%d ",f[n][m]); } return 0; }

热门文章