QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#65423#5139. DFS Order 2magicduck#WA 3ms5524kbC++142.5kb2022-11-30 16:11:162022-11-30 16:11:17

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-30 16:11:17]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:5524kb
  • [2022-11-30 16:11:16]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
template <typename T> inline void read(T &F) {
    int R = 1; F = 0; char CH = getchar();
    for(; !isdigit(CH); CH = getchar()) if(CH == '-') R = -1;
    for(; isdigit(CH); CH = getchar()) F = F * 10 + CH - 48;
    F *= R;
}
inline void file(string str) {
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
}
const LL mod = 998244353;
const int N = 5e2 + 10;
int n, siz[N], t[N]; LL f[N][N], g[N], res[N][N]; vector<int> edge[N];
void dfs(int x, int fa) {
    siz[x] = g[x] = 1; int s = 0; t[x] = fa;
    for(int i : edge[x]) {
        if(fa == i) continue;
        dfs(i, x); siz[x] += siz[i];
        g[x] = g[x] * g[i] % mod;
        s++; g[x] = g[x] * s % mod;
    }
}
LL d[N], sumx[N], sumy[N];
void dp(const vector<int> &s) {
    for(int i = 1; i <= n; i++)
        d[i] = sumx[i] = sumy[i] = 0;
    d[1] = sumx[1] = sumy[1] = 1;
    for(int i : s) {
        for(int j = n; j >= 1; j--) {
            if(i + j <= n) {
                (sumy[i + j] += sumy[j] * sumx[j]) %= mod;
                (d[i + j] += d[j] * sumx[j]) %= mod;
                (sumx[i + j] += d[j] * sumx[j]) %= mod;
            }
            d[j] = d[j] * sumy[j] % mod;
            sumx[j] = sumx[j] * sumy[j] % mod;
            (sumy[j] += d[j]) %= mod;
        }
    }
}
void solve(int x, int fa) {
    if(fa) {
        LL r = 1; vector<int> s;
        for(int i : edge[fa]) {
            if(i != t[fa] && x != i)
                s.emplace_back(siz[i]), r = r * g[i] % mod;
        }
        dp(s);
        for(int i = 1; i <= n; i++) {
            LL res = 0;
            for(int j = 1; j < i; j++)
                res += f[fa][j] * d[i - j] % mod;
            res = res % mod * r % mod;
            f[x][i] = res;
        }
    }
    for(int i = 1; i <= n; i++)
        res[x][i] = f[x][i] * g[x] % mod;
    for(int i : edge[x]) {
        if(i == fa) continue;
        solve(i, x);
    }
}

int main() {
    //file("");
    read(n);
    for(int i = 1; i < n; i++) {
        int x, y; read(x), read(y);
        edge[x].emplace_back(y);
        edge[y].emplace_back(x);
    }    
    dfs(1, 0);
    f[1][1] = 1; solve(1, 0);
    for(int i = 1; i <= n; i++, puts(""))
        for(int j = 1; j <= n; j++)
            cout << res[i][j] << " ";
    #ifdef _MagicDuck
        fprintf(stderr, "# Time: %.3lf s", (double)clock() / CLOCKS_PER_SEC);
    #endif
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 5524kb

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: 2ms
memory: 5524kb

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 4 2 2 6 2 2 2 
0 0 0 4 4 2 4 4 2 0 
0 0 0 0 4 4 2 4 4 2 
0 12 0 0 0 0 0 12 0 0 
0 12 0 0 12 0 0 0 0 0 
0 0 0 4 2 2 6 2 2 2 
0 0 6 6 0 0 0 0 6 6 
0 0 12 0 0 12 0 0 0 0 
0 0 6 6 0 0 0 0 6 6 

result:

wrong answer 17th numbers differ - expected: '8', found: '6'