代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 5;
const ll mod = 998244353LL;
ll num[55], n, k, ans;
ll C[55][55], fac[55], invFac[55], inv[55];
ll pw(ll x, ll y, ll z) {
    ll ret = 1;
    while(y > 0) {
        if((y & 1) == 1) ret = ret*x%mod;
        x = x*x%mod;
        y >>= 1;
    }
    return ret;
}
void init() {
    C[1][0] = C[1][1] = 1;
    for(int i = 2; i <= 50; ++i) {
        C[i][0] = C[i][i] = 1;
        for(int j = 1; j < i; ++j) {
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
            C[i][j] %= mod;
        }
    }
    fac[0] = 1;
    for(int i = 1; i <= 50; ++i) {
        fac[i] = fac[i - 1]*i%mod;
        // printf("%d %lld\n", i, fac[i]);
    }
    invFac[50] = pw(fac[50], mod - 2, mod);
    for(int i = 49; i >= 0; --i) {
        invFac[i] = invFac[i + 1]*(i + 1)%mod;
        // printf("%d %lld\n", i, invFac[i]);
    }
    // for(int i = 1; i <= 5; ++i) {
    //     for(int j = 0; j <= i; ++j) {
    //         printf("%lld ", C[i][j]);
    //     }
    //     puts("");
    // }
}
vector<ll> L[55], Num[55];
void calc(ll tot) {
    // if(num[tot - 1] > 3) return ;
    // puts("-----------------");
    // puts("In calc: ");
    // for(int i = 0; i < tot; ++i) {
    //     printf("%lld ", num[i]);
    // }
    // puts("");
    // puts("-----------------");
    ll d = 0;
    for(int i = 0; i < tot; ++i) {
        d = __gcd(d, num[i]);
    }
    ll lcm = num[0];
    for(int i = 1; i < tot; ++i) {
        lcm = num[i]/__gcd(lcm, num[i])*lcm;
    }
    // printf("%lld %lld\n", d, lcm);
    ll now = C[n][num[0]]*fac[num[0] - 1]%mod, lst = num[0], cnt = 1, rm = n - num[0];
    for(int i = 1; i < tot; ++i) {
        now *= C[rm][num[i]]*fac[num[i] - 1]%mod;
        now %= mod;
        rm -= num[i];
        if(num[i] == num[i - 1]) {
            ++cnt;
        } else {
            now = now*invFac[cnt]%mod;
            lst = num[i];
            cnt = 1;
        }
    }
    now = now*invFac[cnt]%mod;
    L[n].push_back(lcm);
    Num[n].push_back(now);
    // printf("now: %lld\n", now);
}
void dfs(ll pos, ll mi, ll rm) {
    // puts("++++++++++++++++++++++");
    // puts("In dfs: ");
    // printf("pos: %lld mi: %lld rm: %lld gcd: %lld lcm: %lld\n", pos, mi, rm, d, lcm);
    // for(int i = 0; i < pos; ++i) {
    //     printf("%lld ", num[i]);
    // }
    // puts("");
    // puts("++++++++++++++++++++++");
    if(rm == 0) {
        // calc(pos, d, lcm);
        calc(pos);
        return ;
    }
    for(ll i = mi; i <= rm; ++i) { 
        num[pos] = i;
        // ll nd = __gcd(d, i);
        // ll nlcm = i/__gcd(lcm, i)*lcm;
        // if(k%nlcm == 0) dfs(pos + 1, i, rm - i, nd, nlcm);
        dfs(pos + 1, i, rm - i);
    }
}
void GetAnswer() {
    for(ll i = 1; i <= 50; ++i) {
        n = i;
        // if(n == 50)
        dfs(0, 1, n);
        // printf("%lld %d\n", n, L[n].size());
    }
}
int main() {
    init();
    GetAnswer();
    // int T; scanf("%d", &T);
    // for(int cs = 1; cs <= T; ++cs) {
    //     scanf("%lld%lld", &n, &k);
    //     ans = 0;
    //     int sz = L[n].size();
    //     for(int i = 0; i < sz; ++i) {
    //         if(k%L[n][i] == 0) {
    //             ans = (ans + Num[n][i])%mod;
    //         }
    //     }
    //     printf("%lld\n", ans);
    // }
    return 0;
}

评测结果