UVA 12298——Super Poker II

雨点打透心脏的1/2处 2022-07-19 11:56 75阅读 0赞

### 题意： ###

给定一些扑克牌，问这些扑克牌选四色能组成n的方案数，其中遗失了c张牌，这c张不能用，问n从a到b的方案数。

### 思路： ###

分析每一种花色，那么每种花色组成的方案数即为x^1+x^2+x^3+x^5（改花色的牌只有1，2，3，5这四张的时候），那么对比于其他的花色，也是一样，四个花色的方案数相乘，即为所得值，那么很容易来使用FFT，注意可能会超精度，复数要用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);
        }
    };
    
    /* * 进行FFT和IFFT前的反转变换。 * 位置i和j（i二进制反转后位置）互换 * 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("");
        }
    }