QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#641831#5139. DFS Order 2Sound_MediumWA 0ms3792kbC++233.5kb2024-10-15 01:15:592024-10-15 01:16:00

Judging History

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

  • [2024-10-15 01:16:00]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3792kb
  • [2024-10-15 01:15:59]
  • 提交

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'