题解：P4708 画画

JCerZX · 2024-05-23 19:29:45 · 题解

思路

我看了看其他人的代码，好像都是搜索，我就贡献一篇打表吧。首先用了下某神犇的代码（侵权必删）：

#include <bits/stdc++.h>

const int N = 55;
const int M = 125e3 + 5;
const int mod = 998244353;

int n, m, ans;
int fra[N], inv_fra[N], inv[N];
int ex[M], g[N][N], l[N], c[N];
int sze[N], fa[N], cnt_p[N], cnt_e[N];

template <class T>
inline T Max(T x, T y) {return x > y ? x : y;}

inline void add(int &x, int y)
{
    x += y;
    x >= mod ? x -= mod : 0;
}

inline void mul(int &x, int y)
{
    x = 1ll * x * y % mod;
}

inline int quick_pow(int x, int k)
{
    int res = 1;
    while (k)
    {
        if (k & 1)
            res = 1ll * res * x % mod;
        x = 1ll * x * x % mod;
        k >>= 1;
    }
    return res;
}

inline int ufs_find(int x)
{
    return fa[x] == x ? x : fa[x] = ufs_find(fa[x]);
}

inline void ufs_merge(int x, int y, int e)
{
    int tx = ufs_find(x),
        ty = ufs_find(y);
    if (tx != ty)
    {
        if (sze[tx] > sze[ty])
            std::swap(tx, ty);
        fa[tx] = ty;
        sze[ty] += sze[tx];
        cnt_p[ty] += cnt_p[tx];
        cnt_e[ty] += cnt_e[tx] + e;
    }
    else
        cnt_e[ty] += e;
}

inline void solve(int k)
{
    int res = 1;
    for (int i = 1; i <= k; ++i)
        mul(res, inv[l[i]]);
    for (int i = 1; i <= n; ++i)
        mul(res, inv_fra[c[i]]);
    for (int i = 1; i <= k; ++i)
    {
        fa[i] = i;
        cnt_e[i] = 0;
        cnt_p[i] = 0;
        sze[i] = 1;
    }
    for (int i = 1; i <= k; ++i)
    {
        if (!(l[i] & 1))
            ++cnt_p[i];
        mul(res, ex[l[i] - 1 >> 1]);
    }
    for (int i = 1; i < k; ++i)
        for (int j = i + 1; j <= k; ++j)
        {
            int e = g[l[i]][l[j]];
            bool e1 = (l[j] / e) & 1,
                 e2 = (l[i] / e) & 1;
            if (e1 && e2)
                ufs_merge(i, j, e);
            else if (e1)
                cnt_p[ufs_find(i)] += e;
            else if (e2)
                cnt_p[ufs_find(j)] += e;
            else 
                mul(res, ex[e]);
        }
    for (int i = 1; i <= k; ++i)
        if (ufs_find(i) == i)
            mul(res, ex[Max(0, cnt_p[i] - 1) + cnt_e[i] - sze[i] + 1]);
    add(ans, res);
}

inline void dfs(int k, int s, int t)
{
    if (!s)
        return solve(k - 1);
    for (int i = t; i <= s; ++i)
    {
        l[k] = i;
        ++c[i];
        dfs(k + 1, s - i, i);
        --c[i];
    }
}

int main()
{
    scanf("%d", &n);
    fra[0] = 1;
    for (int i = 1; i <= n; ++i)
        fra[i] = 1ll * fra[i - 1] * i % mod;
    inv_fra[n] = quick_pow(fra[n], mod - 2);
    for (int i = n; i >= 1; --i)
        inv_fra[i - 1] = 1ll * inv_fra[i] * i % mod;
    inv[0] = inv[1] = 1;
    for (int i = 2; i <= n; ++i)
        inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
    ex[0] = 1;
    for (int i = 1, im = n * n * n; i <= im; ++i)
        add(ex[i] = ex[i - 1], ex[i - 1]);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            g[i][j] = std::__gcd(i, j);
    dfs(1, n, 1);
    printf("%d\n", ans);
}

稍作修改后得出打表代码：

#include<bits/stdc++.h>
using namespace std;
const int N=53;
int m[N]={0,1,1,2,3,7,16,54,243,2038,33120,1182004,87723296,907260828,445874017,131059413,750854059,85710140,46269468,106575268,569924828,477980796,853121491,916490672,848722293,179336057,577163661,709912061,916083428,988859367,286999618,29547862,713350279,194424628,553076032,609634772,876525030,182311698,148716617,346128108,650982654,373128192,361260409,524419271,834718796,514750301,478609700,386216865,881562716,715225681,602577017};
int main(){
    int n;
    cin>>n;
    cout<<m[n];
    return 0;
}