UVA - 12298 Super Poker II NTT

链接

Vjudge

思路

暴力开个桶，然后统计，不过会T，用ntt或者fft，ntt用个大模数就行了，百度搜索"NTT大模数"。

错误

我也不知道，改着改着自己就A了

思路

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e7+7,mod=39582418599937LL;
char s;
bool vis[N];
ll A[4][N],len[4],r[N];
ll read() {
    ll x=0,f=1;s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
ll mul(ll u,ll v){return ((u*v-(ll)((long double)u/mod*v+1e-8)*mod)%mod+mod)%mod;}
ll q_pow(ll a,ll b) {
    ll ans=1;
    while(b) {
        if(b&1) ans=mul(ans,a);
        a=mul(a,a);
        b>>=1;
    }
    return ans;
}
void ntt(ll *a,ll limit,ll type) {
    for(ll i=0;i<=limit;++i)
        if(i<r[i]) swap(a[i],a[r[i]]);
    for(ll mid=1;mid<limit;mid<<=1) {
        ll Wn=q_pow(5,(mod-1)/(mid<<1));
        for(ll i=0;i<limit;i+=(mid<<1)) {
            for(ll j=0,w=1;j<mid;++j,w=mul(w,Wn)) {
                ll x=a[i+j],y=mul(w,a[i+j+mid]);
                a[i+j]=(x+y)%mod;
                a[i+j+mid]=(x+mod-y)%mod;
            }
        }
    }
    if(type==-1) {
        reverse(&a[1],&a[limit]);
        ll inv=q_pow(limit,mod-2);
        for(ll i=0;i<=limit;++i) a[i]=mul(a[i],inv);
    }
}
void Euler(ll b) {
    for(ll i=2;i<=b;++i)  {
        if(!vis[i]) {
            for(ll j=i+i;j<=b;j+=i) 
                vis[j]=1;
        }
    }
}       
int main() {
    Euler(50000);
    while(233) {
        ll a=read(),b=read(),c=read();
        if(!a&&!b&&!c) break;
        memset(A,0,sizeof(A));
        ll limit=1,l=0;
        for(ll i=2;i<=b;++i) A[0][i]=A[1][i]=A[2][i]=A[3][i]=vis[i];
        for(ll i=1;i<=c;++i) {
            ll x=read();
            if(s=='S') A[0][x]=0;
            else if(s=='H') A[1][x]=0;
            else if(s=='C') A[2][x]=0;          
            else A[3][x]=0;
        }
        while(limit<=4LL*b) limit<<=1,l++;
        for(ll i=0;i<=limit;++i)
            r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
        ntt(A[0],limit,1),ntt(A[1],limit,1),ntt(A[2],limit,1),ntt(A[3],limit,1);
        for(ll i=0;i<=limit;++i) A[0][i]=mul(mul(A[0][i],A[1][i]),mul(A[2][i],A[3][i]));
        ntt(A[0],limit,-1);
        for(ll i=a;i<=b;++i) printf("%lld\n",A[0][i]);
        puts("");
    }
    return 0;
}