QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#505469 | #7609. Colonization | pandapythoner | WA | 0ms | 3940kb | C++23 | 4.7kb | 2024-08-05 05:36:35 | 2024-08-05 05:36:35 |
Judging History
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'