Jzoj4906 组合数问题

题意:noip2016d2t1

我们考虑将每个数字质因数分解来做即可

线性筛求出所有2000以内的质数让后直接暴力分解即可,计算C(i,j)是否为k的倍数,最后加上前缀和

#include<stdio.h> #include<string.h> int w[500],c=0,n,m,t,k,pr[2010]={0}; int l[2010],f[2010][10][2]; int s[2010][2010],S[2010][2010]; void mul(int* v,int i,int d){ for(int j=1;j<=l[i];++j) v[f[i][j][0]]+=d*f[i][j][1]; } int main(){ freopen("problem.in","r",stdin); freopen("problem.out","w",stdout); for(int i=2;i<=2000;++i){ if(!pr[i]){ pr[i]=c; w[c++]=i; } for(int j=0;j<c&&i*w[j]<=2000;++j){ pr[i*w[j]]=-1; if(i%w[j]==0) break; } } for(int x,i=2;i<=2000;++i){ x=i; for(int j=0;w[j]*w[j]<=x;++j) if(x%w[j]==0){ f[i][++l[i]][0]=j; for(;x%w[j]==0;x/=w[j]) ++f[i][l[i]][1]; } if(x>1) { f[i][++l[i]][0]=pr[x]; f[i][l[i]][1]=1; } } for(int i=0;i<c;++i) if(pr[w[i]]!=i) puts("wrong"); scanf("%d%d",&t,&k); int v[300]; for(int i=1;i<=2000;++i){ memset(v,0,sizeof v); for(int j=1;j<=i;++j){ mul(v,i-j+1,1); mul(v,j,-1); s[i][j]=1; for(int x=1;x<=l[k];++x) if(v[f[k][x][0]]<f[k][x][1]) s[i][j]=0; S[i][j]=S[i-1][j]+S[i][j-1]-S[i-1][j-1]+s[i][j]; } for(int j=i+1;j<=2000;++j) S[i][j]=S[i][j-1]; } for(int a,b,i=0;i<t;++i){ scanf("%d%d",&a,&b); printf("%d\n",S[a][b]); } }
相关文章

相关标签/搜索