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;
}