QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#505469#7609. ColonizationpandapythonerWA 0ms3940kbC++234.7kb2024-08-05 05:36:352024-08-05 05:36:35

Judging History

你现在查看的是最新测评结果

  • [2024-08-05 05:36:35]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3940kb
  • [2024-08-05 05:36:35]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;


#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define rep(i, n) for(int i = 0; i < n; i += 1)
#define len(a) ((int)(a).size())


const ll inf = 1e18;
mt19937 rnd(234);

const int maxn = 500;
const int max_rank = __lg(maxn + 1);
int n;
ll mod;
ll dp1[maxn + 1][max_rank + 1];
ll dp2[maxn + 1][max_rank + 1][3];
ll f[maxn + 1], invf[maxn + 1];
ll result[maxn + 1];

ll bin_pow(ll x, ll n) {
    ll rs = 1;
    for (ll i = 1, a = x; i <= n; a = (a * a) % mod, i *= 2)
        if (n & i) rs = rs * a % mod;
    return rs;
}


ll inv(ll x) {
    ll a = bin_pow(x, mod - 2);
    assert(a * x % mod == 1);
    return a;
}


void add(ll& x, ll y) {
    x += y;
    if (x >= mod) x -= mod;
}


int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    cin >> n;
    cin >> mod;
    memset(dp1, 0, sizeof(dp1));
    memset(dp2, 0, sizeof(dp2));
    memset(result, 0, sizeof(result));
    dp2[0][0][2] = 1;
    f[0] = invf[0] = 1;
    for (int i = 1; i <= n; i += 1) {
        f[i] = f[i - 1] * i % mod;
        invf[i] = inv(f[i]);
    }
    for (int tree_rank = 1; tree_rank <= max_rank; tree_rank += 1) {
        for (int tree_size = 1; tree_size <= n; tree_size += 1) {
            add(dp1[tree_size][tree_rank], dp2[tree_size - 1][tree_rank][0]);
            add(dp1[tree_size][tree_rank], dp2[tree_size - 1][tree_rank - 1][1]);
            add(dp1[tree_size][tree_rank], dp2[tree_size - 1][tree_rank - 1][2]);
            for (int sum_size = n; sum_size >= 1; sum_size -= 1) {
                ll val = 1;
                for (int k = 1; sum_size - k * tree_size >= 0; k += 1) {
                    val = val * (dp1[tree_size][tree_rank] + mod - 1 + k) % mod;
                    if (val == 0) break;
                    ll coeff = val * invf[k] % mod;
                    for (int old_max = 0; old_max <= tree_rank; old_max += 1) {
                        rep(count, 3) {
                            int new_count = min(2, k - 1 + (tree_rank == old_max ? count + 1 : 0));
                            add(dp2[sum_size][tree_rank][new_count],
                                dp2[sum_size - k * tree_size][old_max][count] * dp1[tree_size][tree_rank] % mod * coeff % mod);
                        }
                    }
                }
            }

        }
    }
    for (int i = 1; i <= max_rank; i += 1) {
        add(result[i], dp2[n - 1][i - 1][2]);
    }
    for (int rank = 1; rank <= max_rank; rank += 1) {
        ll x = 0;
        auto get_super = [&](int size) {
            return (dp2[size - 1][rank - 1][1] + dp2[size - 1][rank - 1][2]) % mod;
            };
        vector<ll> dp(n + 1);
        for (int lsz = 1; lsz <= n; lsz += 1) {
            for (int rsz = 1; rsz + lsz <= n; rsz += 1) {
                add(dp[lsz + rsz], get_super(lsz) * get_super(rsz) % mod);
            }
        }
        for (int sz = 1; sz <= n; sz += 1) {
            for (int mx = 0; mx < rank; mx += 1) {
                for (int tsz = 1; sz - tsz > 0; tsz += 1) {
                    add(dp[sz], dp[sz - tsz] * dp2[tsz - 1][mx][0] % mod);
                    add(dp[sz], dp[sz - tsz] * dp2[tsz - 1][mx][1] % mod);
                    add(dp[sz], dp[sz - tsz] * dp2[tsz - 1][mx][2] % mod);
                }
            }
        }
        x = dp[n];
        vector<ll> dp_symm(n + 1);
        for (int lsz = 1; 2 * lsz <= n; lsz += 1) {
            add(dp_symm[2 * lsz], get_super(lsz));
        }
        for (int sz = 1; sz <= n; sz += 1) {
            for (int mx = 0; mx < rank; mx += 1) {
                for (int tsz = 1; sz - 2 * tsz > 0; tsz += 1) {
                    add(dp_symm[sz], dp_symm[sz - 2 * tsz] * dp2[tsz - 1][mx][0] % mod);
                    add(dp_symm[sz], dp_symm[sz - 2 * tsz] * dp2[tsz - 1][mx][1] % mod);
                    add(dp_symm[sz], dp_symm[sz - 2 * tsz] * dp2[tsz - 1][mx][2] % mod);
                }
            }
        }
        add(x, dp_symm[n]);
        for (int mid_size = 1; mid_size <= n; mid_size += 1) {
            ll count = 0;
            for (int mx = 0; mx < rank; mx += 1) {
                add(count, dp2[mid_size - 1][mx][0]);
                add(count, dp2[mid_size - 1][mx][1]);
                add(count, dp2[mid_size - 1][mx][2]);
            }
            add(x, count * dp_symm[n - mid_size] % mod);
        }
        x = x * inv(2) % mod;
        add(result[rank], x);
    }
    for (int i = 1; i <= n; i += 1) {
        cout << result[i] << " ";
    }
    cout << "\n";
    return 0;
}

/*

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3688kb

input:

3 100000007

output:

1 0 0 

result:

ok 3 number(s): "1 0 0"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3704kb

input:

6 300000007

output:

1 5 0 0 0 0 

result:

ok 6 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 3776kb

input:

10 1000000007

output:

1 104 1 0 0 0 0 0 0 0 

result:

ok 10 numbers

Test #4:

score: 0
Accepted
time: 0ms
memory: 3768kb

input:

2 739878731

output:

1 0 

result:

ok 2 number(s): "1 0"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3760kb

input:

3 122646779

output:

1 0 0 

result:

ok 3 number(s): "1 0 0"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3908kb

input:

4 457287433

output:

1 1 0 0 

result:

ok 4 number(s): "1 1 0 0"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3688kb

input:

5 1000000007

output:

1 2 0 0 0 

result:

ok 5 number(s): "1 2 0 0 0"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3772kb

input:

6 1000000007

output:

1 5 0 0 0 0 

result:

ok 6 numbers

Test #9:

score: 0
Accepted
time: 0ms
memory: 3700kb

input:

7 763596907

output:

1 10 0 0 0 0 0 

result:

ok 7 numbers

Test #10:

score: 0
Accepted
time: 0ms
memory: 3940kb

input:

8 1000000007

output:

1 22 0 0 0 0 0 0 

result:

ok 8 numbers

Test #11:

score: 0
Accepted
time: 0ms
memory: 3700kb

input:

9 729507523

output:

1 46 0 0 0 0 0 0 0 

result:

ok 9 numbers

Test #12:

score: -100
Wrong Answer
time: 0ms
memory: 3688kb

input:

11 488473873

output:

1 230 10 0 0 0 0 0 0 0 0 

result:

wrong answer 3rd numbers differ - expected: '4', found: '10'