QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#667567 | #5139. DFS Order 2 | HHAZ | WA | 1ms | 5816kb | C++20 | 3.7kb | 2024-10-23 00:16:06 | 2024-10-23 00:16:06 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int>pii;
typedef pair<ll,ll>pll;
typedef pair<ld,ld>pdd;
typedef pair<ll, pair<ll, ll> > plpair;
typedef vector<int> vi;
typedef vector<ll> vl;
#define endl '\n'
#define rep(i, a, b) for (ll i = (a); i <= (b); ++i)
#define per(i, a, b) for(ll i = (a); i >= (b); --i)
#define debug(x) cout<<#x<<": "<<x<<endl
#define lowbit(id) id & (-id)
#define fi first
#define sec second
#define lc id<<1
#define rc id<<1|1
#define sz(x) (int)(x).size()
#define all(t) (t).begin(), (t).end()
#define meh {cout<<"NO"<<endl;return;}
#define yay {cout<<"YES"<<endl;return;}
#define vin(v) for(auto&x:v)cin>>x;
#define print(v) for (auto x: v)cout<<x<<' ';cout<<endl;
#define sqrt(x) sqrtl(x)
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
const ll N = 505;
const int mod = 998244353;
ll n;
ll dp[N][N], ans[N][N];
ll f[N], val[N], siz[N], son[N], g[N];
vector<ll>ve[N];
ll qsm(ll n,ll b, ll Mod = 998244353){
n = n % Mod;
ll s = 1,a = n;
while(b){
a = a % Mod;
if(b&1)
s = s * a;
b >>= 1;
a = a * a;
s = s % Mod;
}
return s;
}
void init_dfs(ll u, ll fa) {
siz[u]++;
ll j = 1;
for(auto v : ve[u]) {
if(v != fa) {
init_dfs(v, u);
siz[u] += siz[v];
son[u]++;
j *= val[v];
j %= mod;
}
}
val[u] = j * f[son[u]] % mod;
}
void dfs(ll u, ll fa) {
rep(i, 0, son[u]) {
rep(j, 0, siz[u]) {
dp[i][j] = 0;
}
}
dp[0][0] = 1;
ll d = 1;
for(auto v : ve[u]) {
if(v != fa) {
d *= val[v];
per(i, son[u], 1) {
per(j, siz[u], siz[v]) {
dp[i][j] += dp[i - 1][j - siz[v]];
dp[i][j] %= mod;
}
}
}
}
for(auto v : ve[u]) {
if(v != fa) {
rep(i, 0, 500) {
g[i] = 0;
}
rep(i, 1, son[u]) {
rep(j, siz[v], siz[u]) {
dp[i][j] -= dp[i - 1][j - siz[v]];
dp[i][j] = (dp[i][j] + mod) % mod;
// if(v==3 && dp[i][j]) cout << i << ' ' << j << ' ' << dp[i][j] << endl;
}
}
rep(i, 0, son[u] - 1) {
rep(j, 0, siz[u]) {
g[j] += ((((dp[i][j] * f[i]) % mod) * f[son[u] - 1 - i]) % mod) * d % mod;
g[j] % mod;
// if(v==3 && dp[i][j]) cout << i << ' ' << j << ' ' << ((((dp[i][j] * f[i]) % mod) * f[son[u] - 1 - i]) % mod) * d % mod << endl;
}
}
// if(v==3)
// rep(j, 0, son[u]) {
// debug(g[j]);
// }
rep(i, 1, n) {
rep(j, i + 1, n) {
if(ans[u][i]) {
ans[v][j] += g[j - i - 1];
ans[v][j] %= mod;
}
}
}
per(i, son[u], 1) {
per(j, siz[u], siz[v]) {
dp[i][j] += dp[i - 1][j - siz[v]];
dp[i][j] %= mod;
}
}
}
}
for(auto v : ve[u]) {
if(v != fa) {
dfs(v, u);
}
}
}
void solve() {
cin >> n;
f[0] = 1;
rep(i, 1, n) {
f[i] = f[i - 1] * i % mod;
}
rep(i, 2, n) {
ll u, v;
cin >> u >> v;
ve[u].push_back(v);
ve[v].push_back(u);
}
init_dfs(1, 0);
ans[1][1] = val[1];
dfs(1, 0);
rep(i, 1, n) {
rep(j, 1, n) {
cout << ans[i][j] << " \n"[j == n];
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
// cin >> T;
// cout.flush();
// ofstream outfile("C:\\Users\\86187\\OneDrive\\桌面\\1.txt");
// outfile << "a[1]=0;a[2]=1;";
// ll l = 1e7 + 1;
// rep(i, 3, 1e9) {
// printf("%lld\n", i);
// ll x = (i - 1) * ((a[i - 1] + a[i - 2]) % mod);
// x %= mod;
// if(i == l) {
// outfile << "a[" << i << "]=" << x << ";";
// }
// if(i == l + 1) {
// outfile << "a[" << i << "]=" << x << ";";
// l += 1e7;
// }
// }
while(T--) {
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5684kb
input:
5 1 2 1 3 3 4 3 5
output:
4 0 0 0 0 0 2 0 0 2 0 2 2 0 0 0 0 1 2 1 0 0 1 2 1
result:
ok 25 numbers
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 5816kb
input:
10 9 2 9 6 10 5 1 5 1 6 9 3 5 8 4 3 7 9
output:
24 0 0 0 0 0 0 0 0 0 0 0 0 2 1 1 4 1 1 2 0 0 0 2 2 2 2 2 2 0 0 0 0 0 1 1 1 1 1 1 0 12 0 0 0 0 0 12 0 0 0 12 0 0 12 0 0 0 0 0 0 0 0 2 1 1 4 1 1 2 0 0 1 1 0 0 0 0 1 1 0 0 6 0 0 6 0 0 0 0 0 0 1 1 0 0 0 0 1 1
result:
wrong answer 14th numbers differ - expected: '4', found: '2'