QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#766968	#9566. Topology	Stelor	TL	55ms	112856kb	C++20	6.4kb	2024-11-20 19:28:44	2024-11-20 19:28:45

Judging History

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

[2024-11-20 19:28:45]
评测

测评结果：TL
用时：55ms
内存：112856kb

查看

[2024-11-20 19:28:44]
提交

answer

#include<bits/stdc++.h>
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)

using namespace std;
using LL=long long;
template<class T>
constexpr T power(T a, long long b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}

template<int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(LL x) : x{norm(x % getMod())} {}

    static int Mod;
    constexpr static int getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(int Mod_) {
        Mod = Mod_;
    }
    constexpr int norm(int x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr int val() const {
        return x;
    }
    explicit constexpr operator int() const {
        return x;
    }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }
    constexpr MInt &operator*=(MInt rhs) & {
        x = 1LL * x * rhs.x % getMod();
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) & {
        return *this *= rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
        LL v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
};

template<>
int MInt<0>::Mod = 998244353;

template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

constexpr int P = 998244353;
using Z = MInt<P>;

using ll=long long;

const int N=5010;
int n,sz[N];
Z C[N][N],dp[N][N],f[N],pre[N],fac[N];
vector<int> v[N];

void init()
{
    fac[0]=1;
    for(int i=1;i<N;++i) fac[i]=fac[i-1]*i;
    C[0][0]=1;
    for(int i=1;i<N;++i)
    {
        for(int j=0;j<N;++j)
        {
            if(!j) C[i][0]=1;
            if(j>i) break;
            C[i][j]=C[i-1][j]+C[i-1][j-1];
        }
    }
}

void initDfs(int u,int fa){
    sz[u]=1;
    Z tmp=1;
    f[u]=1;
    for(auto j:v[u]){
        if(j==fa) continue;
        initDfs(j,u);
        sz[u]+=sz[j];
        tmp=tmp*fac[sz[j]];
        f[u]=f[u]*f[j];
    }
    f[u]=f[u]*fac[sz[u]-1]/tmp;
}
void dfs(int fa,int pa){
    Z t1=1;
    for(auto u:v[fa]){
        if(u==pa) continue;
        t1=t1*f[u];
        t1=t1/fac[sz[u]];
    }
    for(auto u:v[fa]){
        if(u==pa) continue;
        Z t2=fac[sz[fa]-sz[u]-1];
        for(int i=0;i<=n;++i) pre[i]=0;
        for(int i=1;i<=n;++i){
            if(n-i-sz[u]>=0&&sz[fa]-sz[u]-1>=0)
            pre[i]=dp[fa][i]*C[n-i-sz[u]][sz[fa]-sz[u]-1];
            else break;
        }
        for(int i=1;i<=n;++i){
            pre[i]=pre[i-1]+pre[i];
        }
        for(int i=1;i<=n;++i){
            dp[u][i]=pre[i-1]*t1*t2/f[u]*fac[sz[u]];
        }
        dfs(u,fa);
    }
}
void solve(){
    cin >> n;
    for(int i=2;i<=n;++i){
        int x;
        cin >> x;
        v[x].push_back(i);
    }
    init();
    initDfs(1,0);
    dp[1][1]=1;
    dfs(1,0);
    for(int i=1;i<=n;++i){
        Z ans=dp[i][i]*f[i]*C[n-i][sz[i]-1];
        cout<<ans<<" ";
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 7ms

memory: 105556kb

input:

4
1 1 2

output:

3 2 1 2

result:

ok 4 number(s): "3 2 1 2"

Test #2:

score: 0

Accepted

time: 8ms

memory: 102088kb

input:

9
1 1 2 2 3 3 4 5

output:

672 420 180 160 152 108 120 170 210

result:

ok 9 numbers

Test #3:

score: 0

Accepted

time: 8ms

memory: 103176kb

input:

2
1

output:

1 1

result:

ok 2 number(s): "1 1"

Test #4:

score: 0

Accepted

time: 55ms

memory: 112572kb

input:

500
1 2 3 4 5 6 7 7 8 10 8 10 11 4 11 12 12 17 15 13 21 21 22 5 16 9 24 28 28 19 29 27 17 33 23 3 33 27 30 9 25 34 16 26 30 34 46 45 41 14 43 49 43 35 39 37 26 48 52 58 51 56 51 55 19 48 63 36 67 69 54 60 71 61 29 40 32 77 73 55 66 42 77 72 71 69 62 83 46 64 88 39 83 36 89 94 47 98 57 61 38 80 78 88...

output:

331058271 331058271 107893248 201481008 579367731 934007150 548415590 60830816 948776140 565765713 126668425 603509050 491206892 433369091 271511598 706737964 70425819 69672788 713120782 734952162 267434947 720007515 670449595 828144080 372921049 434477621 877300187 307269573 636190001 793011806 327...

result:

ok 500 numbers

Test #5:

score: 0

Accepted

time: 50ms

memory: 112596kb

input:

500
1 2 3 4 5 2 6 8 9 10 11 12 13 14 15 16 7 18 19 17 21 20 22 24 25 26 23 27 29 30 2 28 31 34 35 36 37 38 39 33 40 42 41 43 45 46 17 47 49 35 50 52 44 53 9 55 54 57 58 59 61 60 62 64 65 66 67 68 69 70 63 71 27 73 25 70 75 78 79 80 75 80 81 84 72 86 87 85 89 90 91 88 92 16 71 93 53 94 99 10 100 12 9...

output:

199957339 199957339 748333395 805642956 810719215 216632308 964282353 833358220 623717061 424992417 41206958 5217119 281930684 668877517 802111716 240451113 155227928 771617392 672767638 673855602 761694864 890967936 403166179 449035439 448814216 496258330 91156115 884637248 925796040 876356346 3811...

result:

ok 500 numbers

Test #6:

score: 0

Accepted

time: 50ms

memory: 112628kb

input:

500
1 2 1 4 3 6 5 8 7 9 11 10 12 13 15 14 17 16 18 20 21 19 22 24 23 25 26 28 27 30 29 32 33 31 34 36 37 35 38 40 41 42 43 39 44 46 47 45 48 50 49 51 53 54 52 56 55 58 59 60 61 57 63 62 65 66 64 67 69 70 71 72 73 74 75 76 68 77 78 79 81 80 83 84 85 82 87 88 89 86 90 91 93 94 95 96 97 92 99 98 100 10...

output:

187816035 355846039 636462310 682484799 14615667 17420694 667957129 920773234 729673969 411376216 888381123 826027316 567944447 754373007 910160630 717957076 351581515 786718944 83290109 442478607 895300579 856543135 635821052 404405371 646574856 177948738 754298629 824600386 979643534 991141839 946...

result:

ok 500 numbers

Test #7:

score: 0

Accepted

time: 41ms

memory: 112728kb

input:

500
1 2 3 4 5 6 7 6 9 9 11 10 13 14 11 14 17 18 19 5 10 17 20 15 12 22 25 19 18 28 28 32 30 23 15 23 22 30 12 38 35 41 2 38 21 42 40 25 7 27 37 49 41 16 39 50 45 36 59 33 59 16 34 51 35 43 54 4 45 64 20 32 37 74 50 27 24 54 73 26 61 63 68 46 56 60 52 83 66 60 21 51 65 8 92 77 48 88 93 67 53 42 74 10...

output:

427192209 427192209 23428540 404862570 37642846 503529666 371081925 254270895 921949697 428219013 402374560 324846667 395339852 778833345 147767470 733058880 358816361 71418780 554069977 130001346 128392987 484159059 134194129 243653359 516885764 231025182 612595461 494287189 387500567 550886195 417...

result:

ok 500 numbers

Test #8:

score: 0

Accepted

time: 50ms

memory: 112856kb

input:

500
1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

output:

329123348 329123348 618048964 618048964 618048964 618048964 618048964 618048964 618048964 618048964 618048964 618048964 618048964 618048964 618048964 618048964 618048964 618048964 618048964 618048964 618048964 618048964 618048964 618048964 618048964 618048964 618048964 618048964 618048964 618048964 ...

result:

ok 500 numbers

Test #9:

score: 0

Accepted

time: 43ms

memory: 112708kb

input:

500
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 19 19 19 19 23 19 19 19 27 28 19 19 19 24 32 19 19 35 21 36 40 41 42 39 19 34 29 19 19 19 37 33 26 52 48 44 30 57 46 25 56 22 58 43 54 38 45 61 65 59 62 20 50 60 47 72 75 73 51 66 31 53 49 71 83 63 68 70 55 76 1 64 78 86 74 87 81 94 82 99 89 97 92 ...

output:

853424916 94140539 412971244 235944608 263389091 489983454 601309014 819943428 486761409 617130546 686025380 122859767 819931429 563270436 884428627 886775343 47583182 426881586 177783742 240713239 583332417 714069050 77150690 574574846 465537641 189786313 312927405 763991274 371298436 953710348 715...

result:

ok 500 numbers

Test #10:

score: 0

Accepted

time: 54ms

memory: 110420kb

input:

500
1 2 2 4 2 5 7 8 2 9 11 12 13 14 15 16 17 18 10 19 21 22 2 18 25 2 26 27 23 30 2 31 33 3 34 36 37 38 28 39 2 20 41 44 45 2 40 46 49 48 51 52 25 43 53 29 55 56 46 59 50 62 57 61 54 63 45 45 2 65 71 67 73 59 46 74 77 49 78 77 78 43 81 72 80 84 64 87 77 78 2 2 76 86 62 68 71 95 96 2 82 2 89 60 94 69...

output:

471850367 471850367 182262350 404570423 107733458 816781731 922698877 850608239 433937054 883062365 287376567 851878007 830978534 761469013 140873496 758088636 641403760 236550255 968037976 36602630 940485631 261386090 728452257 816781731 556050534 883310107 938450533 689162937 196110016 463212341 8...

result:

ok 500 numbers

Test #11:

score: -100

Time Limit Exceeded

input:

5000
1 2 3 4 5 6 7 4 8 7 10 12 10 14 2 15 17 17 18 15 6 21 19 12 14 11 20 20 27 29 28 32 24 34 21 11 33 9 25 13 34 39 42 35 36 44 3 47 9 44 5 38 53 37 41 13 39 38 22 28 57 59 54 59 61 66 54 64 58 26 49 23 62 25 69 73 48 45 67 77 68 23 24 81 71 47 87 62 73 65 55 88 74 36 95 29 26 75 80 32 66 87 75 98...