UVA12298

Super Poker II

我居然没想到这个牌的点数不是个位数。。。我是深必。。。

来回换了无数次模数，又提交了一大堆。。。

应该是普通的加法卷积？

只不过答案可能很大，FFT 是一个不错的选择（FFT 丢精度应该没有想象的厉害，吧？）。

然后也可以去 NTT 模数表那边贺模数，贺个大一点的（虽然我也不知道上界是啥，但实际测试 998244353 不行），然后我贺了个 31525197391593473，原根是 3。

先筛出来合数并把这些系数赋值为 1，然后把丢掉的牌赋为 0。

然后四次 DFT，卷积完之后 IDFT 回去。

时间复杂度 $O(n\log n)$。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll __int128
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;
inline void writeln(ll x) {write(x);putchar(10);}

const ll N=4e6,mo=31525197391593473ll,G=3;

namespace Aeft{
  inline ll Pow(ll b,ll p) {
    ll res=1;while(p) {if(p&1) res=res*b%mo;b=b*b%mo;p>>=1;}return res;
  }
}using Aeft::Pow;

const ll invG=Pow(G,mo-2);

ll x,y,z,n,m,invn,cnt;
ll rev[N+5],s[N+5],h[N+5],c[N+5],d[N+5];
ll prime[N+5];
bool f[N+5];

inline void NTT(ll *f,bool op) {
  for(ll i=0;i<n;i++) if(i<rev[i]) swap(f[i],f[rev[i]]);
  for(ll p=2;p<=n;p<<=1) {
    ll len=p>>1,tG=Pow(op?invG:G,(mo-1)/p);
    for(ll k=0;k<n;k+=p) {
      for(ll l=k,buf=1;l<k+len;l++,buf=buf*tG%mo) {
        ll t=buf*f[len+l]%mo;
        f[len+l]=f[l]-t;if(f[len+l]<0) f[len+l]+=mo;
        f[l]=f[l]+t;if(f[l]>mo) f[l]-=mo;
      }
    }
  }
  if(op) {for(ll i=0;i<n;i++) f[i]=f[i]*invn%mo;}
}

inline void Init() {
  f[1]=1;
  for(ll i=1;i<=N;i++) {
    if(!f[i]) {prime[++cnt]=i;}
    for(ll j=1;j<=cnt&&i*prime[j]<=N;j++) {
      f[i*prime[j]]=1;if(i%prime[j]==0) break;
    }
  }
}

inline void Init_() {
  for(m=y*8,n=1;n<m;n<<=1);invn=Pow(n,mo-2);
  for(ll i=0;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)?(n>>1):0);
  for(ll i=0;i<n;i++) {s[i]=h[i]=c[i]=d[i]=0;}
  for(ll i=4;i*4<n;i++) {
    if(f[i]) {s[i]=h[i]=c[i]=d[i]=f[i];}
  }
}

inline ll Transtonum(char *s,ll n) {
  ll res=0;for(ll i=0;i<n;i++) {res*=10ll;res+=s[i]-48;}return res;
}

int main() {

  Init();

  for(;;) {
    x=read();y=read();z=read();
    if(x==0&&y==0&&z==0) break;
    Init_();
    for(ll i=1;i<=z;i++) {
      char ch[10];scanf("%s",ch);
      ll len=strlen(ch);ll tmp=Transtonum(ch,len-1);
      if(ch[len-1]=='S') {s[tmp]=0;}
      if(ch[len-1]=='H') {h[tmp]=0;}
      if(ch[len-1]=='C') {c[tmp]=0;}
      if(ch[len-1]=='D') {d[tmp]=0;}
    }
    NTT(s,0);NTT(h,0);NTT(c,0);NTT(d,0);
    for(ll i=0;i<n;i++) s[i]=s[i]*h[i]%mo;
    for(ll i=0;i<n;i++) s[i]=s[i]*c[i]%mo;
    for(ll i=0;i<n;i++) s[i]=s[i]*d[i]%mo;
    NTT(s,1);
    for(ll i=x;i<=y;i++) writeln(s[i]);
    putchar('\n');
  }

  return 0;
}