QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#641831 | #5139. DFS Order 2 | Sound_Medium | WA | 0ms | 3792kb | C++23 | 3.5kb | 2024-10-15 01:15:59 | 2024-10-15 01:16:00 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int mod = 998244353;
int qmi(int a,int b,int p){
int res=1;
while(b){
if(b&1)res=res*a%p;
a=a*a%p;
b>>=1;
}
return res;
}
int inv(int a,int p){
return qmi(a,p-2,p);
}
void solve () {
int n;
cin >> n;
vector<int>pre(n+1);
pre[0]=1;
vector<int>far(n+1,-1);
for(int i=1;i<=n;i++)pre[i]=pre[i-1]*i%mod;
// vector <int> fac (n + 1);
// fac[0] = 1;
// for (int i = 1; i <= n; i ++) {
// fac[i] = fac[i - 1] * i % mod;
// }
vector <vector <int>> e (n+1);
for (int i = 1; i < n; i ++) {
int x, y;
cin >> x >> y;
// x --; y --;
e[x].push_back (y);
e[y].push_back (x);
}
vector <int> sz (n+1, 1);
vector <int> dp (n+1, 1);
auto dfs1 = [&] (auto &&self, int x, int fa) -> void {
int son = 0;
far[x]=fa;
for (auto y : e[x]) {
if (y == fa) {
continue;
}
son ++;
self (self, y, x);
sz[x] += sz[y];
dp[x] *= dp[y];
dp[x] %= mod;
}
dp[x] = dp[x] * pre[son] % mod;
};
dfs1 (dfs1,1, -1);
vector ans (n+1, vector <int> (n + 1));
vector res (n+1, vector <int> (n + 1));
ans[1][1]= 0;
res[1][1]= 1;
// cerr<<e[1].size();
auto dfs2 = [&] (auto &&self, int x, int fa) -> void {
if(fa!=-1){
int sszz=e[fa].size()-1-(far[fa]!=-1);
// cerr<<x<<" "<<far[x]<<" "<<sszz<<endl;
int siz=sz[fa]-sz[x];
// cerr<<x<<" "<<siz<<endl;
vector<vector<int>>dp1(siz+2,vector<int>(sszz+1,0));
dp1[0][0]=1;
int sum=0;
for(auto y:e[fa]){
if(y==far[fa])continue;
if(y==x)continue;
if(!sum)sum=1;
auto ndp=dp1;
sum=sum*dp[y]%mod;
for(int i=siz-1;i>=sz[y];i--){
// cerr<<siz-1-sz[y]<<endl;
for(int j=sszz;j>=1;j--){
ndp[i][j]=dp1[i-sz[y]][j-1]*dp[y]%mod;
}
}
dp1=move(ndp);
}
vector<int>b(n+1,0);
vector<int>c(n+1,0);
// b[0]=1;
for(int i=0;i<=sszz;i++){
for(int j=0;j<=siz-1;j++){
c[j]=(c[j]+dp1[j][i]*pre[i]%mod)%mod;
// b[j]=(c[j]+dp1[j][i]*pre[i]%mod*pre[sszz-i]%mod*dp[x]%mod*inv(dp1[j][i],mod)%mod)%mod;
if(dp1[j][i])
b[j]=(b[j]+pre[i]*pre[sszz-i]%mod*sum%mod*dp[x]%mod)%mod;
// if(x==2){
// cerr<<c[j]<<" "<<b[j]<<endl;
// }
// if(x==2&&j==0)cerr<<b[j]<<endl;
}
}
// if(x==2){
// for(int i=1;i<=n;i++)cerr<<b[i]<<" ";cerr<<endl;
// cerr<<dp[2]<<endl;
// }
for(int i=1;i<=n;i++){
for(int j=0;j<=n;j++){
if(i+j+1>n)continue;
ans[x][i+j+1]+=res[fa][i]*b[j]%mod;
ans[x][i+j+1]%=mod;
res[x][i+j+1]+=res[fa][i]*c[j]%mod;
res[x][i+j+1]%=mod;
}
}
}
for(auto y:e[x]){
if(y==fa)continue;
self(self,y,x);
}
};
dfs2 (dfs2, 1, -1);
ans[1][1]=dp[1];
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j ++) {
cout << (ans[i][j]) << " \n"[j == n];
// cerr << (res[i][j]) << " \n"[j == n];
}
}
}
signed main () {
ios::sync_with_stdio (false);
cin.tie (nullptr);
int T = 1;
// cin >> T;
while (T --) {
solve ();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3620kb
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: 3792kb
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 0 6 2 0 4 0 0 0 2 1 2 4 2 4 0 0 0 0 0 0 0 0 0 0 0 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 6 2 2 4 0 0 1 1 0 0 0 0 6 6 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 6 6
result:
wrong answer 14th numbers differ - expected: '4', found: '2'