UVA12298 Super Poker II 题解

Description

Solution

其实就是个 NTT 多项式乘法板子。

~~我不会告诉你我一开始还推了半天生成函数（然后发现直接把 5e4 的系数全都直接赋值就完了QwQ~~

那么本题的解法就是这样=-=

开 4 个数组，表示 4 种花色的多项式。对于每一组数据，暴力把每一位的系数都赋上：

合数位系数都为 1，质数位都为 0，再把被删掉牌的位系数改为 0。

注意：~~不知道为什么~~在本题中 1 被看成了质数，系数为 0。

然后把 4 个数组都卷起来就完了。

然后就没啦。

还有一个小问题，一般的模数会被卡，我是直接用的 kls 的模数，得用 __int128。

Code

#include <bits/stdc++.h>
#define Int __int128

using namespace std;

namespace IO{
    inline Int read(char &ch){
        Int x = 0;
        ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const Int N = 1e6 + 10;
const Int P = 5e4;
const Int mod = 4179340454199820289ll;
const Int G = 3, Gi = 1393113484733273430ll;
Int n, m, k;
Int a[N], b[N], c[N], d[N], e[N], rev[N];
Int p[N], tot;
bool vis[N];
char ch;

namespace NTT{
    Int lim, len;

    inline Int qpow(Int a, Int b){
        Int res = 1;
        while(b){
            if(b & 1) res = res * a % mod;
            a = a * a % mod, b >>= 1;
        }
        return res;
    }

    inline void get_rev(Int n){
        lim = 1, len = 0;
        while(lim <= n) lim <<= 1, ++len;
        for(int i = 0; i <= lim; ++i) p[i] = (p[i >> 1] >> 1) | ((i & 1) << (len - 1));
    }

    inline void ntt(Int A[], Int lim, Int type){
        for(int i = 0; i < lim; ++i)
            if(i < p[i]) swap(A[i], A[p[i]]);
        for(int mid = 1; mid < lim; mid <<= 1){
            Int Wn = qpow(type == 1 ? G : Gi, (mod - 1) / (mid << 1));
            for(int i = 0; i < lim; i += (mid << 1)){
                Int w = 1;
                for(int j = 0; j < mid; ++j, w = w * Wn % mod){
                    Int x = A[i + j], y = w * A[i + j + mid] % mod;
                    A[i + j] = (x + y) % mod;
                    A[i + j + mid] = (x - y + mod) % mod;
                }
            }
        }
        if(type == 1) return;
        Int inv = qpow(lim, mod - 2);
        for(int i = 0; i < lim; ++i) A[i] = A[i] * inv % mod;
    }

    inline void Mul(Int n, Int m, Int a[], Int b[]){
        get_rev(n + m);
        ntt(a, lim, 1), ntt(b, lim, 1);
        for(int i = 0; i <= lim; ++i) a[i] = a[i] * b[i] % mod;
        ntt(a, lim, -1);
    }
}
using namespace NTT;

inline void euler(){
    for(int i = 2; i <= P; ++i){
        if(!vis[i]) p[++tot] = i;
        for(int j = 1; j <= tot && i * p[j] <= P; ++j){
            vis[i * p[j]] = 1;
            if(i % p[j] == 0) break;
        }
    }
}

inline void del(){
    int x = read(ch);
    if(ch == 'S') a[x] = 0;
    if(ch == 'H') b[x] = 0;
    if(ch == 'C') c[x] = 0;
    if(ch == 'D') d[x] = 0;
}

signed main(){
    euler();
    while(1){
        n = read(ch), m = read(ch), k = read(ch);
        if(!n && !m && !k) break;
        memset(a, 0, sizeof(a)), memset(b, 0, sizeof(b));
        memset(c, 0, sizeof(c)), memset(d, 0, sizeof(d));
        for(int i = 0; i <= m; ++i)
            a[i] = b[i] = c[i] = d[i] = vis[i];
        for(int i = 1; i <= k; ++i) del();
        Mul(m, m, a, b), Mul(m, m, c, d), Mul(m << 1, m << 1, a, c);
        for(int i = n; i <= m; ++i) write(a[i]), puts("");
        puts("");
    }
    return 0;
}

\[\_EOF\_ \]