题解 UVA12298 【Super Poker II】

· · 题解

做的第一道真正意义上的生成函数题。

列出显然的生成函数

F(x)=\prod_{i=1}^{4} \sum_{k=2}^{\infty}[k\notin prime,k\notin lost] k

其中 k\notin prime 表示出选的必须是合数，k\notin lost 表示出选的必须没有丢失。

所以我们需要列出4个多项式 A,B,C,D，分别代表 黑桃，红心，草花，方块 四个花色中每个数字是否可选。

for(register ll i=0;i<=bi;i++) a[i]=b[i]=c[i]=d[i]=vst[i]; //必须是合数
for(register ll i=1;i<=ci;i++) {
    int g; char ch; cin>>g>>ch;
    if(ch=='S') a[g]=0;
    else if(ch=='H') b[g]=0;
    else if(ch=='C') c[g]=0;
    else if(ch=='D') d[g]=0;
}

然后求出 F(x)，（即四个多项式的乘积）输出 第 a 项到第 b 项的系数即可。

说一些细节问题。一开始用了 FFT，然后发现精度不够（具体看讨论版中我发的那个求助帖）。然后用了 NTT，结果发现模数太小（这也只能怪我没数清楚……）。用了 NTT 大模数（AKrry的），结果发现 longlong 对于我貌似会炸，于是怒开 __int128，所以我的程序常数极大。

#include<bits/stdc++.h>
#define ll __int128
//全开int128是个非常耗时的行为，建议部分地方开
using namespace std;
const ll N=5e4+9,mod=4179340454199820289,g=3,ig=1393113484733273430;
ll n,m,l,r[N<<5],a[N<<5],b[N<<5],c[N<<5],d[N<<5];

ll ksm(ll a,ll b){
    if(b==0) return 1;
    else if(b==1) return a;
    else return ksm(a*a%mod,b/2)*(b%2?a:1)%mod;
}

void ntt(ll *f,ll type){} //NTT，也不放了，常数过大

bool vst[N];
void prime(ll n); //线性筛，不放了

signed main() { 
    prime(50000);
    while(1) {
        long long ai,bi,ci;scanf("%lld%lld%lld",&ai,&bi,&ci);
        n=m=bi;
        memset(a,0,sizeof(b)), memset(b,0,sizeof(b)),
        memset(c,0,sizeof(c)), memset(d,0,sizeof(d)); //这里常数过大，建议只用清理到需要的范围
        if(!ai&&!bi&&!ci) break;
        for(register ll i=0;i<=bi;i++) a[i]=b[i]=c[i]=d[i]=vst[i];
        for(register ll i=1;i<=ci;i++) {
            int g; char ch; cin>>g>>ch;
            if(ch=='S') a[g]=0;
            else if(ch=='H') b[g]=0;
            else if(ch=='C') c[g]=0;
            else if(ch=='D') d[g]=0;
        }
        //从这里到下面都是板子
        m<<=3; l=0;
        for(n=1;n<=m;n*=2) l++;
        for(ll i=0;i<=n;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
        ntt(a,1), ntt(b,1), ntt(c,1), ntt(d,1);
        for(ll i=0;i<=n;i++) a[i]=a[i]*b[i]%mod*c[i]%mod*d[i]%mod;
        ntt(a,-1);
        for(int i=ai;i<=bi;i++) printf("%lld\n",(long long)a[i]);
        puts("");
    } 
    return 0;
}