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;

}