QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#331779 | #4811. Be Careful | Tokido_Saya | WA | 1ms | 8128kb | C++14 | 5.2kb | 2024-02-18 19:22:55 | 2024-02-18 19:22:55 |
Judging History
answer
// Sea, You & Me
#include<bits/stdc++.h>
#define LL long long
#define DB double
#define MOD 998244353
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define lowbit(x) ((-x) & x)
#define MP make_pair
#define MT make_tuple
#define VI vector<int>
#define VL vector<LL>
#define VII VI::iterator
#define VLI VL::iterator
#define all(x) x.begin(), x.end()
#define EB emplace_back
#define PII pair<int, int>
#define SI set<int>
#define SII SI::iterator
#define fi first
#define se second
using namespace std;
template<typename T> void chkmn(T &a, const T b) { (a > b) && (a = b); }
template<typename T> void chkmx(T &a, const T b) { (a < b) && (a = b); }
void Inc(int &a, const int &b) { ((a += b) >= MOD) && (a -= MOD); }
void Dec(int &a, const int &b) { ((a -= b) < 0) && (a += MOD); }
void Mul(int &a, const int &b) { a = 1LL * a * b % MOD; }
void Sqr(int &a) { a = 1LL * a * a % MOD; }
int inc(const int &a, const int &b) { return (a + b >= MOD) ? a + b - MOD : a + b; }
int dec(const int &a, const int &b) { return (a - b < 0) ? a - b + MOD : a - b; }
int mul(const int &a, const int &b) { return 1LL * a * b % MOD; }
int sqr(const int &a) { return 1LL * a * a % MOD; }
int qwqmi(int x, int k = MOD - 2)
{
int res = 1;
while(k)
{
if(k & 1) Mul(res, x);
k >>= 1, Sqr(x);
}
return res;
}
template<typename T> void read(T &x)
{
x = 0;
int f = 1;
char ch = getchar();
while(!isdigit(ch))
{
if(ch == '-')
f = -1;
ch = getchar();
}
while(isdigit(ch))
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x = x * f;
}
const int N = 205;
int n;
int qwq[N][N];
// qwq[i][j] : i^j
int deg[N], dcnt[N];
// dcnt[i] : the number of sons with deg <= i
vector<int> G[N], S1, S2;
// S1 is the set of sons with deg <= B, and S2 otherwise (leaves are not in consideration)
int f[N][N], suf[N][N];
// f[u][i] : the number when w[u] = i
// suf[u][i] : f[u][i] + f[u][i + 1] + ... + f[u][n]
int g[1 << 19];
// g[S] : the number of : take account of color <= B, the set of unselected colors is exactly S
int h[1 << 19][N];
// h[S][j] : the number of : take account the subset S of S2, order them to fill j unselected colors among [0, i](i is now possible ans)
int coef[1 << 19];
// coef[S] : the number of : take account the subset S of S2, order the color of sons in S to be > i(i is now possible ans)
void dfs(int u, int fa)
{
// leaf
if((int)G[u].size() == 1 && u != 1)
{
for(int i = 0; i <= n; ++i)
{
f[u][i] = 1;
suf[u][i] = n - i + 1;
}
return;
}
// series of preprocess
int leafcnt = 0;
for(auto v : G[u])
{
if(v == fa) continue;
dfs(v, u); ++deg[u];
if(!deg[v]) ++leafcnt;
}
memset(dcnt, 0, sizeof(dcnt));
for(auto v : G[u])
{
if(v == fa) continue;
++dcnt[deg[v]];
}
for(int i = 1; i <= n; ++i)
dcnt[i] += dcnt[i - 1];
int B = 0, minx = N;
for(int i = 0; i <= 18; ++i)
if(i + dcnt[n] - dcnt[i] < minx)
minx = i + dcnt[n] - dcnt[i], B = i;
S1.clear(), S2.clear();
for(auto v : G[u])
{
if(v == fa) continue;
if(!deg[v]) continue;
if(deg[v] <= B) S1.EB(v);
else S2.EB(v);
}
int L = (int)S2.size();
const int M1 = (1 << (B + 1));
const int M2 = (1 << L);
// calc g
// First, calculate the number of "the set of unselected colors is at least S"
for(int S = 0; S < M1; ++S)
{
g[S] = 1;
for(auto v : S1)
{
int sum = 0;
for(int i = 0; i <= B; ++i)
if((!(S >> i) & 1))
Inc(sum, f[v][i]);
Mul(g[S], sum);
}
}
// Then, use SOSDP to calculate the true g[S]
for(int i = 0; i <= B; ++i)
for(int S = 0; S < M1; ++S)
if(!((S >> i) & 1))
Dec(g[S], g[S ^ (1 << i)]);
// calc ans
for(int _S = 0; _S < M1; ++_S)
{
if(!g[_S]) continue;
for(int S = 0; S < M2; ++S)
for(int i = 0; i <= deg[u]; ++i)
h[S][i] = 0;
h[0][0] = g[_S];
for(int i = 0; i <= deg[u]; ++i)
{
// calc f
if((_S & (1 << i)) || i > B) // may be w[u]
{
coef[0] = 1;
for(int S = 1; S < M2; ++S)
{
int x = __builtin_ctz(S);
coef[S] = mul(coef[S ^ (1 << x)], suf[S2[x]][i + 1]);
}
// inclusion and exclusion (actually superset inversion)
for(int S = 0; S < M2; ++S)
for(int j = 0; j <= deg[u]; ++j)
{
int val = mul(coef[(M2 - 1) ^ S], mul(h[S][j], qwq[n - j][leafcnt]));
if(j & 1) Dec(f[u][i], val); else Inc(f[u][i], val);
}
}
// calc h
for(int j = i; j >= 0; --j)
{
// if i is free, consider to fill it
if((_S & (1 << i)) || i > B)
{
for(int S = 0; S < M2; ++S)
Inc(h[S][j + 1], h[S][j]);
}
// SOSDP
for(int k = 0; k < L; ++k)
for(int S = 0; S < M2; ++S)
if(!((S >> k) & 1))
Inc(h[S ^ (1 << k)][j], mul(h[S][j], f[S2[k]][i]));
}
}
}
// after-process
for(int i = n; i >= 0; --i)
suf[u][i] = inc(suf[u][i + 1], f[u][i]);
while(!f[u][deg[u]]) --deg[u];
}
int main()
{
read(n);
for(int i = 1; i < n; ++i)
{
int x, y;
read(x), read(y);
G[x].EB(y), G[y].EB(x);
}
for(int i = 1; i <= n; ++i)
{
qwq[i][0] = 1;
for(int j = 1; j <= n; ++j)
qwq[i][j] = mul(qwq[i][j - 1], i);
}
dfs(1, 0);
for(int i = 0; i <= n; ++i)
printf("%d\n", f[1][i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 8000kb
input:
5 1 2 1 3 2 4 2 5
output:
55 127 34 0 0 0
result:
ok 6 numbers
Test #2:
score: 0
Accepted
time: 1ms
memory: 7992kb
input:
8 1 2 1 3 1 4 1 5 1 6 6 7 6 8
output:
69632 265534 133905 47790 12636 1944 0 0 0
result:
ok 9 numbers
Test #3:
score: 0
Accepted
time: 1ms
memory: 8048kb
input:
3 1 2 2 3
output:
1 3 0 0
result:
ok 4 number(s): "1 3 0 0"
Test #4:
score: 0
Accepted
time: 1ms
memory: 8116kb
input:
2 1 2
output:
2 1 0
result:
ok 3 number(s): "2 1 0"
Test #5:
score: 0
Accepted
time: 1ms
memory: 8128kb
input:
10 1 8 1 9 6 1 2 1 1 4 1 10 1 5 7 1 3 1
output:
1755647 612579511 359376750 200038110 104287680 49974120 21379680 7771680 2177280 362880 0
result:
ok 11 numbers
Test #6:
score: 0
Accepted
time: 1ms
memory: 8004kb
input:
10 2 8 2 9 6 2 2 1 2 4 2 10 2 5 7 2 3 2
output:
114358881 100000000 0 0 0 0 0 0 0 0 0
result:
ok 11 numbers
Test #7:
score: 0
Accepted
time: 1ms
memory: 8008kb
input:
10 7 8 8 9 6 5 2 1 3 4 9 10 4 5 7 6 3 2
output:
10 1 0 0 0 0 0 0 0 0 0
result:
ok 11 numbers
Test #8:
score: 0
Accepted
time: 1ms
memory: 8012kb
input:
10 3 6 2 4 4 9 8 4 2 5 10 5 3 7 2 1 1 3
output:
27510 31142 102399 0 0 0 0 0 0 0 0
result:
ok 11 numbers
Test #9:
score: 0
Accepted
time: 1ms
memory: 8008kb
input:
14 10 3 6 2 2 8 3 13 1 3 1 2 3 14 4 2 9 3 12 3 2 5 7 2 11 3
output:
930962871 780146137 253920328 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 15 numbers
Test #10:
score: 0
Accepted
time: 1ms
memory: 8048kb
input:
20 7 6 2 6 5 1 17 12 9 13 12 18 3 2 9 1 2 1 12 6 10 9 14 2 4 1 6 8 11 2 16 9 13 19 8 15 20 5
output:
572808214 694156482 763085092 958730326 465749894 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 21 numbers
Test #11:
score: -100
Wrong Answer
time: 1ms
memory: 8052kb
input:
21 6 12 11 13 1 7 8 14 1 18 5 4 1 2 16 11 21 1 9 10 15 17 1 9 1 8 1 20 1 3 1 4 19 16 11 1 15 10 3 6
output:
778184256 0 710233310 10751559 76447757 959248417 24632015 777459888 618380400 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
wrong answer 2nd numbers differ - expected: '242901486', found: '0'