题解 UVA12298 【Super Poker II】
_lgswdn
2020-06-13 20:51:19
做的第一道真正意义上的生成函数题。
列出显然的生成函数
$$
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$，分别代表 黑桃，红心，草花，方块 四个花色中每个数字是否可选。
```cpp
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```，所以我的程序常数极大。
```cpp
#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;
}
```