題意：

給定一些撲克牌，問這些撲克牌選四色能組成n的方案數(shù)，其中遺失了c張牌，這c張不能用，問n從a到b的方案數(shù)。

思路：

分析每一種花色，那么每種花色組成的方案數(shù)即為x^1+x^2+x^3+x^5（改花色的牌只有1，2，3，5這四張的時候），那么對比于其他的花色，也是一樣，四個花色的方案數(shù)相乘，即為所得值，那么很容易來使用FFT，注意可能會超精度，復(fù)數(shù)要用long double。

code：

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std;const long double PI=acos(-1.0); typedef long double ld;struct complex {long double l,r;complex(ld ll=0.0,ld rr=0.0){l=ll;r=rr;}complex operator +(const complex& B){return complex(l+B.l,r+B.r);}complex operator - (const complex& B){return complex(l-B.l,r-B.r);}complex operator *(const complex& B){return complex(l*B.l-r*B.r,l*B.r+B.l*r);} };/** 進(jìn)行FFT和IFFT前的反轉(zhuǎn)變換。* 位置i和j（i二進(jìn)制反轉(zhuǎn)后位置）互換* len必須是2的冪*/ void change(complex y[],int len){int i,j,k;for (int i=1,j=len/2;i<len-1;i++){if (i<j) swap(y[i],y[j]);k=len/2;while (j>=k){j-=k;k>>=1;}if (j<k) j+=k;} } /** 做FFT* len必須為2^k形式，* on==1時是DFT，on==-1時是IDFT*/ void fft(complex y[],int len,int on){change(y,len);for (int h=2;h<=len;h<<=1){complex wn(cos(-on*2*PI/h),sin(-on*2*PI/h));for (int j=0;j<len;j+=h){complex w(1,0);for (int k=j;k<j+h/2;k++){complex u=y[k];complex t=w*y[k+h/2];y[k]=u+t;y[k+h/2]=u-t;w=w*wn;}}}if (on==-1){for (int i=0;i<len;i++){y[i].l/=len;}} }const int N=262144; const int M=50005; complex s[N],c[N],d[N],h[N]; int vis[M],pri[M],tot; void getP(int n){memset(vis,0,sizeof(vis));tot=0;//vis[0]=vis[1]=1;for (int i=2;i<n;i++){if (!vis[i]) pri[tot++]=i;for (int j=0;j<tot&&i*pri[j]<n;j++){vis[i*pri[j]]=1;if (i%pri[j]==0) break;}} }int main() {getP(M);int A,B,C;while (~scanf("%d%d%d",&A,&B,&C),A+B+C){int len=1;while(len<=B) len<<=1;len<<=2;for (int i=0;i<=len;i++) s[i]=h[i]=c[i]=d[i]=complex(0,0);for(int i=0; i<B; ++i) if(vis[i]) s[i]=h[i]=c[i]=d[i]=complex(1,0);for (int i=0;i<C;i++){char ch[3];scanf("%s",ch);int ln=strlen(ch),t;sscanf(ch,"%d",&t);if (ch[ln-1]=='S') s[t].l=0;if (ch[ln-1]=='H') h[t].l=0;if (ch[ln-1]=='C') c[t].l=0;if (ch[ln-1]=='D') d[t].l=0;}fft(s,len,1);fft(h,len,1);fft(c,len,1);fft(d,len,1);for (int i=0;i<=len;i++) h[i]=h[i]*s[i]*c[i]*d[i];fft(h,len,-1);for (int i=A;i<=B;i++) printf("%.0f\n",fabs((double)h[i].l));puts("");} }

總結(jié)

以上是生活随笔為你收集整理的UVA 12298——Super Poker II的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。