FFT(快速傅里叶变换):UVAoj 12298 - Super Poker II

  题目:就是现在有一堆扑克里面的牌有无数张, 每种合数的牌有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了。

 #include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const long double PI=acos(-1.0);
struct complex{
long double r,i;
complex(long double r_=0.0,long double i_=0.0){
r=r_;i=i_;
}
complex operator +(const complex &a)const{
return complex(r+a.r,i+a.i);
}
complex operator -(const complex &a)const{
return complex(r-a.r,i-a.i);
}
complex operator *(const complex &a)const{
return complex(r*a.r-i*a.i,a.r*i+a.i*r);
}
}A[<<],B[<<],C[<<],D[<<]; void Rader(complex *a,int len){
int k;
for(int i=,j=len>>;i<len-;i++){
if(i<j)swap(a[i],a[j]);
k=len>>;
while(j>=k){
j-=k;
k>>=;
}
j+=k;
}
} void FFT(complex *a,int len,int on){
Rader(a,len);
for(int h=;h<=len;h<<=){
complex wn(cos(-on*PI*2.0/h),sin(-on*PI*2.0/h));
for(int j=;j<len;j+=h){
complex w(,);
for(int k=j;k<j+(h>>);k++){
complex x=a[k];
complex y=a[k+(h>>)]*w;
a[k]=x+y;
a[k+(h>>)]=x-y;
w=w*wn;
}
}
}
if(on==-)
for(int i=;i<len;i++)
a[i].r/=len;
return;
} bool num[];
void Shaker(){
for(int i=;i<=;i++)
if(!num[i])
for(int j=i<<;j<=;j+=i)
num[j]=true;
} int main(){
#ifndef ONLINE_JUDGE
//freopen("","r",stdin);
//freopen("","w",stdout);
#endif
Shaker();
int a,b,c,len;
while(scanf("%d%d%d",&a,&b,&c)==&&(a||b||c)){
len=;
while(len<=b<<)len<<=;
memset(A,,sizeof(A));
memset(B,,sizeof(B));
memset(C,,sizeof(C));
memset(D,,sizeof(D));
for(int i=;i<=b;i++)
if(num[i])
A[i]=B[i]=C[i]=D[i]=complex(,);
int id;
char ch;
while(c--){
scanf("%d%c",&id,&ch);
if(ch=='S')A[id]=complex(,);
else if(ch=='H')B[id]=complex(,);
else if(ch=='C')C[id]=complex(,);
else D[id]=complex(,);
} FFT(A,len,);FFT(B,len,);FFT(C,len,);FFT(D,len,);
for(int i=;i<len;i++)
A[i]=A[i]*B[i]*C[i]*D[i];
FFT(A,len,-);
for(int i=a;i<=b;i++)
printf("%lld\n",(long long)(A[i].r+0.5));
printf("\n");
}
return ;
}
上一篇:oracle中dual表的使用


下一篇:深入理解Javascript