题目：就是现在有一堆扑克里面的牌有无数张, 每种合数的牌有4中不同花色各一张(0, 1都不是合数), 没有质数或者大小是0或者1的牌现在这堆牌中缺失了其中的 c 张牌, 告诉你a, b, c接下来c张不同的丢失的牌, 然后求从这堆牌中拿出各种花色的牌各一张, 得到的点数和是k的种数有多少种(一种组合算作一种), 需要全部所有的a <= k <= b的k对应的结果。
让一个多项式的每一位代表一个数字（总共4个多项式），发现如果第一位代表数字0，则其乘法的性质刚好符合加法的条件（第i位与第j位相加，那么这个会转移到第i+j-1位上，实际上是指三个大小：分别是i-1，j-1，i+j-2，（就是各减了一个1），此时与加法吻合），就可以用FFT了。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <cmath> 5 using namespace std; 6 const long double PI=acos(-1.0); 7 struct complex{ 8 long double r,i; 9 complex(long double r_=0.0,long double i_=0.0){ 10 r=r_;i=i_; 11 } 12 complex operator +(const complex &a)const{ 13 return complex(r+a.r,i+a.i); 14 } 15 complex operator -(const complex &a)const{ 16 return complex(r-a.r,i-a.i); 17 } 18 complex operator *(const complex &a)const{ 19 return complex(r*a.r-i*a.i,a.r*i+a.i*r); 20 } 21 }A[1<<20],B[1<<20],C[1<<20],D[1<<20]; 22 23 24 void Rader(complex *a,int len){ 25 int k; 26 for(int i=1,j=len>>1;i<len-1;i++){ 27 if(i<j)swap(a[i],a[j]); 28 k=len>>1; 29 while(j>=k){ 30 j-=k; 31 k>>=1; 32 } 33 j+=k; 34 } 35 } 36 37 void FFT(complex *a,int len,int on){ 38 Rader(a,len); 39 for(int h=2;h<=len;h<<=1){ 40 complex wn(cos(-on*PI*2.0/h),sin(-on*PI*2.0/h)); 41 for(int j=0;j<len;j+=h){ 42 complex w(1,0); 43 for(int k=j;k<j+(h>>1);k++){ 44 complex x=a[k]; 45 complex y=a[k+(h>>1)]*w; 46 a[k]=x+y; 47 a[k+(h>>1)]=x-y; 48 w=w*wn; 49 } 50 } 51 } 52 if(on==-1) 53 for(int i=0;i<len;i++) 54 a[i].r/=len; 55 return; 56 } 57 58 bool num[50010]; 59 void Shaker(){ 60 for(int i=2;i<=50000;i++) 61 if(!num[i]) 62 for(int j=i<<1;j<=50000;j+=i) 63 num[j]=true; 64 } 65 66 int main(){ 67 #ifndef ONLINE_JUDGE 68 //freopen("","r",stdin); 69 //freopen("","w",stdout); 70 #endif 71 Shaker(); 72 int a,b,c,len; 73 while(scanf("%d%d%d",&a,&b,&c)==3&&(a||b||c)){ 74 len=1; 75 while(len<=b<<2)len<<=1; 76 memset(A,0,sizeof(A)); 77 memset(B,0,sizeof(B)); 78 memset(C,0,sizeof(C)); 79 memset(D,0,sizeof(D)); 80 for(int i=2;i<=b;i++) 81 if(num[i]) 82 A[i]=B[i]=C[i]=D[i]=complex(1,0); 83 int id; 84 char ch; 85 while(c--){ 86 scanf("%d%c",&id,&ch); 87 if(ch=='S')A[id]=complex(0,0); 88 else if(ch=='H')B[id]=complex(0,0); 89 else if(ch=='C')C[id]=complex(0,0); 90 else D[id]=complex(0,0); 91 } 92 93 FFT(A,len,1);FFT(B,len,1);FFT(C,len,1);FFT(D,len,1); 94 for(int i=0;i<len;i++) 95 A[i]=A[i]*B[i]*C[i]*D[i]; 96 FFT(A,len,-1); 97 for(int i=a;i<=b;i++) 98 printf("%lld ",(long long)(A[i].r+0.5)); 99 printf(" "); 100 } 101 return 0; 102 }