QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#88194	#5357. 芒果冰加了空气	Rainybunny	100 ✓	84ms	71256kb	C++23	1.9kb	2023-03-15 15:19:08	2023-03-15 15:19:10

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-03-15 15:19:10]
评测

测评结果：100
用时：84ms
内存：71256kb

查看

[2023-03-15 15:19:08]
提交

answer

/*+Rainybunny+*/

#include <bits/stdc++.h>

#define rep(i, l, r) for (int i = l, rep##i = r; i <= rep##i; ++i)
#define per(i, r, l) for (int i = r, per##i = l; i >= per##i; --i)

const int MAXN = 5e3, MOD = 1e9 + 7;
int n, fac[MAXN + 5], ifac[MAXN + 5], siz[MAXN + 5], f[MAXN + 5][MAXN + 5];
std::vector<int> adj[MAXN + 5];

inline int mul(const int u, const int v) { return 1ll * u * v % MOD; }
inline void subeq(int& u, const int v) { (u -= v) < 0 && (u += MOD); }
inline int sub(int u, const int v) { return (u -= v) < 0 ? u + MOD : u; }
inline void addeq(int& u, const int v) { (u += v) >= MOD && (u -= MOD); }
inline int add(int u, const int v) { return (u += v) < MOD ? u : u - MOD; }
inline int mpow(int u, int v) {
    int ret = 1;
    for (; v; u = mul(u, u), v >>= 1) ret = mul(ret, v & 1 ? u : 1);
    return ret;
}

inline void init() {
    fac[0] = 1;
    rep (i, 1, n) fac[i] = mul(i, fac[i - 1]);
    ifac[n] = mpow(fac[n], MOD - 2);
    per (i, n - 1, 0) ifac[i] = mul(i + 1, ifac[i + 1]);
}

inline void solve(const int u, const int fa) {
    f[u][1] = siz[u] = 1;
    for (int v: adj[u]) if (v != fa) {
        solve(v, u);
        static int g[MAXN + 5], h[MAXN + 5];
        g[siz[v] + 1] = 0;
        per (i, siz[v], 0) g[i] = add(g[i + 1], f[v][i]);
        rep (i, 0, siz[v]) g[i] = mul(g[i], ifac[i]);
        memset(h + 1, 0, siz[u] + siz[v] << 2);
        rep (i, 1, siz[u]) rep (j, 0, siz[v]) {
            addeq(h[i + j], mul(f[u][i], g[j]));
        }
        memcpy(f[u] + 1, h + 1, siz[u] + siz[v] << 2), siz[u] += siz[v];
    }
    rep (i, 1, siz[u]) f[u][i] = mul(f[u][i], fac[i - 1]);
}

int main() {
    scanf("%d", &n), init();
    rep (i, 2, n) {
        int u, v; scanf("%d %d", &u, &v);
        adj[u].push_back(v), adj[v].push_back(u);
    }

    solve(1, 0);
    printf("%d\n", int(std::accumulate(f[1] + 1, f[1] + n + 1, 0ll) % MOD));
    return 0;
}

Source code, Language: C++23

这程序好像有点Bug，我给组数据试试？

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5

Accepted

Test #1:

score: 5

Accepted

time: 2ms

memory: 3688kb

input:

output:

result:

ok single line: '310862'

Test #2:

score: 0

Accepted

time: 2ms

memory: 3836kb

input:

output:

result:

ok single line: '64804'

Test #3:

score: 0

Accepted

time: 2ms

memory: 3636kb

input:

output:

result:

ok single line: '258182'

Test #4:

score: 0

Accepted

time: 2ms

memory: 5620kb

input:

output:

result:

ok single line: '16796'

Test #5:

score: 0

Accepted

time: 2ms

memory: 3844kb

input:

output:

result:

ok single line: '78384'

Test #6:

score: 0

Accepted

time: 2ms

memory: 3840kb

input:

output:

result:

ok single line: '38896'

Test #7:

score: 0

Accepted

time: 0ms

memory: 3700kb

input:

output:

result:

ok single line: '609656'

Test #8:

score: 0

Accepted

time: 2ms

memory: 3632kb

input:

output:

result:

ok single line: '64804'

Test #9:

score: 0

Accepted

time: 2ms

memory: 3664kb

input:

output:

result:

ok single line: '118638'

Test #10:

score: 0

Accepted

time: 2ms

memory: 3700kb

input:

output:

result:

ok single line: '22438'

Test #11:

score: 0

Accepted

time: 2ms

memory: 3660kb

input:

output:

result:

ok single line: '16796'

Test #12:

score: 0

Accepted

time: 2ms

memory: 3692kb

input:

output:

result:

ok single line: '82316'

Test #13:

score: 0

Accepted

time: 2ms

memory: 3860kb

input:

output:

result:

ok single line: '13700'

Test #14:

score: 0

Accepted

time: 1ms

memory: 3720kb

input:

output:

result:

ok single line: '3996'

Test #15:

score: 0

Accepted

time: 0ms

memory: 3684kb

input:

output:

result:

ok single line: '3490'

Test #16:

score: 0

Accepted

time: 1ms

memory: 3828kb

input:

output:

result:

ok single line: '1430'

Test #17:

score: 0

Accepted

time: 0ms

memory: 3712kb

input:

output:

result:

ok single line: '1430'

Test #18:

score: 0

Accepted

time: 0ms

memory: 3712kb

input:

output:

result:

ok single line: '3232'

Test #19:

score: 0

Accepted

time: 2ms

memory: 5732kb

input:

output:

result:

ok single line: '8970'

Test #20:

score: 0

Accepted

time: 2ms

memory: 3684kb

input:

output:

result:

ok single line: '3996'

Test #21:

score: 0

Accepted

time: 0ms

memory: 3680kb

input:

output:

result:

ok single line: '3332'

Test #22:

score: 0

Accepted

time: 0ms

memory: 3712kb

input:

output:

result:

ok single line: '1870'

Test #23:

score: 0

Accepted

time: 2ms

memory: 3680kb

input:

output:

result:

ok single line: '2416'

Test #24:

score: 0

Accepted

time: 1ms

memory: 3708kb

input:

output:

result:

ok single line: '2802'

Test #25:

score: 0

Accepted

time: 0ms

memory: 3844kb

input:

3
1 2
2 3

output:

result:

ok single line: '5'

Test #26:

score: 0

Accepted

time: 2ms

memory: 3872kb

input:

output:

result:

ok single line: '78904'

Subtask #2:

score: 10

Accepted

Test #27:

score: 10

Accepted

time: 84ms

memory: 71004kb

input:

output:

138172849

result:

ok single line: '138172849'

Test #28:

score: 0

Accepted

time: 18ms

memory: 33128kb

input:

output:

34585647

result:

ok single line: '34585647'

Test #29:

score: 0

Accepted

time: 51ms

memory: 51968kb

input:

output:

179814607

result:

ok single line: '179814607'

Test #30:

score: 0

Accepted

time: 3ms

memory: 22152kb

input:

output:

997745350

result:

ok single line: '997745350'

Test #31:

score: 0

Accepted

time: 5ms

memory: 23196kb

input:

output:

459486613

result:

ok single line: '459486613'

Test #32:

score: 0

Accepted

time: 84ms

memory: 70436kb

input:

output:

276300910

result:

ok single line: '276300910'

Test #33:

score: 0

Accepted

time: 25ms

memory: 38084kb

input:

output:

161112418

result:

ok single line: '161112418'

Test #34:

score: 0

Accepted

time: 27ms

memory: 39844kb

input:

output:

501208825

result:

ok single line: '501208825'

Test #35:

score: 0

Accepted

time: 9ms

memory: 31636kb

input:

output:

995483163

result:

ok single line: '995483163'

Test #36:

score: 0

Accepted

time: 30ms

memory: 41736kb

input:

output:

324344238

result:

ok single line: '324344238'

Subtask #3:

score: 10

Accepted

Dependency #1:

100%

Accepted

Test #37:

score: 10

Accepted

time: 2ms

memory: 5764kb

input:

output:

85351498

result:

ok single line: '85351498'

Test #38:

score: 0

Accepted

time: 0ms

memory: 3708kb

input:

output:

469047999

result:

ok single line: '469047999'

Test #39:

score: 0

Accepted

time: 2ms

memory: 3776kb

input:

output:

564120378

result:

ok single line: '564120378'

Test #40:

score: 0

Accepted

time: 2ms

memory: 3908kb

input:

output:

663766512

result:

ok single line: '663766512'

Test #41:

score: 0

Accepted

time: 1ms

memory: 3880kb

input:

output:

476848595

result:

ok single line: '476848595'

Test #42:

score: 0

Accepted

time: 1ms

memory: 3772kb

input:

output:

488457335

result:

ok single line: '488457335'

Test #43:

score: 0

Accepted

time: 2ms

memory: 5900kb

input:

output:

752198316

result:

ok single line: '752198316'

Test #44:

score: 0

Accepted

time: 2ms

memory: 3876kb

input:

output:

542252149

result:

ok single line: '542252149'

Test #45:

score: 0

Accepted

time: 1ms

memory: 3884kb

input:

output:

194863442

result:

ok single line: '194863442'

Test #46:

score: 0

Accepted

time: 1ms

memory: 3888kb

input:

output:

23651915

result:

ok single line: '23651915'

Test #47:

score: 0

Accepted

time: 2ms

memory: 3740kb

input:

output:

492545226

result:

ok single line: '492545226'

Test #48:

score: 0

Accepted

time: 0ms

memory: 3908kb

input:

output:

351974281

result:

ok single line: '351974281'

Test #49:

score: 0

Accepted

time: 1ms

memory: 3708kb

input:

output:

781206475

result:

ok single line: '781206475'

Test #50:

score: 0

Accepted

time: 2ms

memory: 3912kb

input:

output:

859563531

result:

ok single line: '859563531'

Test #51:

score: 0

Accepted

time: 2ms

memory: 3764kb

input:

output:

376484809

result:

ok single line: '376484809'

Test #52:

score: 0

Accepted

time: 3ms

memory: 5780kb

input:

output:

785968691

result:

ok single line: '785968691'

Test #53:

score: 0

Accepted

time: 2ms

memory: 3696kb

input:

output:

931047734

result:

ok single line: '931047734'

Test #54:

score: 0

Accepted

time: 2ms

memory: 5656kb

input:

output:

162400297

result:

ok single line: '162400297'

Test #55:

score: 0

Accepted

time: 2ms

memory: 3876kb

input:

output:

250839719

result:

ok single line: '250839719'

Test #56:

score: 0

Accepted

time: 2ms

memory: 3736kb

input:

output:

219471148

result:

ok single line: '219471148'

Test #57:

score: 0

Accepted

time: 2ms

memory: 5700kb

input:

output:

194863442

result:

ok single line: '194863442'

Test #58:

score: 0

Accepted

time: 2ms

memory: 3724kb

input:

output:

493588236

result:

ok single line: '493588236'

Test #59:

score: 0

Accepted

time: 0ms

memory: 3768kb

input:

output:

399365910

result:

ok single line: '399365910'

Test #60:

score: 0

Accepted

time: 2ms

memory: 3716kb

input:

output:

24503169

result:

ok single line: '24503169'

Subtask #4:

score: 25

Accepted

Dependency #3:

100%

Accepted

Test #61:

score: 25

Accepted

time: 2ms

memory: 4064kb

input:

output:

207339010

result:

ok single line: '207339010'

Test #62:

score: 0

Accepted

time: 2ms

memory: 3892kb

input:

output:

444163693

result:

ok single line: '444163693'

Test #63:

score: 0

Accepted

time: 2ms

memory: 5816kb

input:

output:

253999939

result:

ok single line: '253999939'

Test #64:

score: 0

Accepted

time: 1ms

memory: 6064kb

input:

output:

404981769

result:

ok single line: '404981769'

Test #65:

score: 0

Accepted

time: 2ms

memory: 3888kb

input:

output:

454043074

result:

ok single line: '454043074'

Test #66:

score: 0

Accepted

time: 0ms

memory: 5920kb

input:

output:

832905030

result:

ok single line: '832905030'

Test #67:

score: 0

Accepted

time: 1ms

memory: 5836kb

input:

output:

805899378

result:

ok single line: '805899378'

Test #68:

score: 0

Accepted

time: 2ms

memory: 3820kb

input:

output:

705490172

result:

ok single line: '705490172'

Test #69:

score: 0

Accepted

time: 2ms

memory: 5788kb

input:

output:

634401149

result:

ok single line: '634401149'

Test #70:

score: 0

Accepted

time: 2ms

memory: 3856kb

input:

output:

269904773

result:

ok single line: '269904773'

Test #71:

score: 0

Accepted

time: 2ms

memory: 5572kb

input:

output:

310957820

result:

ok single line: '310957820'

Test #72:

score: 0

Accepted

time: 2ms

memory: 3920kb

input:

output:

529454602

result:

ok single line: '529454602'

Test #73:

score: 0

Accepted

time: 1ms

memory: 5736kb

input:

output:

742352534

result:

ok single line: '742352534'

Test #74:

score: 0

Accepted

time: 0ms

memory: 5880kb

input:

output:

570704962

result:

ok single line: '570704962'

Test #75:

score: 0

Accepted

time: 0ms

memory: 5784kb

input:

output:

767444667

result:

ok single line: '767444667'

Test #76:

score: 0

Accepted

time: 2ms

memory: 3936kb

input:

output:

735270809

result:

ok single line: '735270809'

Test #77:

score: 0

Accepted

time: 0ms

memory: 3908kb

input:

output:

859967454

result:

ok single line: '859967454'

Test #78:

score: 0

Accepted

time: 2ms

memory: 5888kb

input:

output:

707392314

result:

ok single line: '707392314'

Test #79:

score: 0

Accepted

time: 2ms

memory: 6024kb

input:

output:

552215869

result:

ok single line: '552215869'

Test #80:

score: 0

Accepted

time: 0ms

memory: 5888kb

input:

output:

214555805

result:

ok single line: '214555805'

Test #81:

score: 0

Accepted

time: 3ms

memory: 3924kb

input:

output:

11910602

result:

ok single line: '11910602'

Test #82:

score: 0

Accepted

time: 0ms

memory: 5784kb

input:

output:

234907268

result:

ok single line: '234907268'

Test #83:

score: 0

Accepted

time: 2ms

memory: 4076kb

input:

output:

206263445

result:

ok single line: '206263445'

Test #84:

score: 0

Accepted

time: 0ms

memory: 5968kb

input:

output:

731555292

result:

ok single line: '731555292'

Subtask #5:

score: 20

Accepted

Dependency #4:

100%

Accepted

Test #85:

score: 20

Accepted

time: 2ms

memory: 12148kb

input:

output:

23954621

result:

ok single line: '23954621'

Test #86:

score: 0

Accepted

time: 2ms

memory: 12036kb

input:

output:

952035142

result:

ok single line: '952035142'

Test #87:

score: 0

Accepted

time: 4ms

memory: 12088kb

input:

output:

875356010

result:

ok single line: '875356010'

Test #88:

score: 0

Accepted

time: 1ms

memory: 11996kb

input:

output:

706621405

result:

ok single line: '706621405'

Test #89:

score: 0

Accepted

time: 4ms

memory: 12200kb

input:

output:

972656594

result:

ok single line: '972656594'

Test #90:

score: 0

Accepted

time: 0ms

memory: 12276kb

input:

output:

537838315

result:

ok single line: '537838315'

Test #91:

score: 0

Accepted

time: 4ms

memory: 12064kb

input:

output:

967361004

result:

ok single line: '967361004'

Test #92:

score: 0

Accepted

time: 2ms

memory: 11716kb

input:

output:

513218946

result:

ok single line: '513218946'

Test #93:

score: 0

Accepted

time: 0ms

memory: 11804kb

input:

output:

16995876

result:

ok single line: '16995876'

Test #94:

score: 0

Accepted

time: 1ms

memory: 12136kb

input:

output:

471041228

result:

ok single line: '471041228'

Test #95:

score: 0

Accepted

time: 1ms

memory: 12104kb

input:

output:

972656594

result:

ok single line: '972656594'

Test #96:

score: 0

Accepted

time: 4ms

memory: 12240kb

input:

output:

500366412

result:

ok single line: '500366412'

Test #97:

score: 0

Accepted

time: 1ms

memory: 14284kb

input:

output:

436627764

result:

ok single line: '436627764'

Test #98:

score: 0

Accepted

time: 4ms

memory: 12212kb

input:

output:

182295868

result:

ok single line: '182295868'

Test #99:

score: 0

Accepted

time: 0ms

memory: 12320kb

input:

output:

566795449

result:

ok single line: '566795449'

Test #100:

score: 0

Accepted

time: 4ms

memory: 12096kb

input:

output:

964271954

result:

ok single line: '964271954'

Test #101:

score: 0

Accepted

time: 2ms

memory: 12076kb

input:

output:

631187518

result:

ok single line: '631187518'

Test #102:

score: 0

Accepted

time: 3ms

memory: 12260kb

input:

output:

810088955

result:

ok single line: '810088955'

Test #103:

score: 0

Accepted

time: 2ms

memory: 12124kb

input:

output:

690741801

result:

ok single line: '690741801'

Test #104:

score: 0

Accepted

time: 2ms

memory: 12008kb

input:

output:

572499025

result:

ok single line: '572499025'

Test #105:

score: 0

Accepted

time: 1ms

memory: 12064kb

input:

output:

907316692

result:

ok single line: '907316692'

Test #106:

score: 0

Accepted

time: 2ms

memory: 11960kb

input:

output:

960051317

result:

ok single line: '960051317'

Test #107:

score: 0

Accepted

time: 1ms

memory: 12188kb

input:

output:

682235485

result:

ok single line: '682235485'

Test #108:

score: 0

Accepted

time: 0ms

memory: 12104kb

input:

output:

728680806

result:

ok single line: '728680806'

Subtask #6:

score: 30

Accepted

Dependency #5:

100%

Accepted

Test #109:

score: 30

Accepted

time: 36ms

memory: 50524kb

input:

output:

796804219

result:

ok single line: '796804219'

Test #110:

score: 0

Accepted

time: 73ms

memory: 48248kb

input:

output:

225232488

result:

ok single line: '225232488'

Test #111:

score: 0

Accepted

time: 59ms

memory: 71092kb

input:

output:

254007764

result:

ok single line: '254007764'

Test #112:

score: 0

Accepted

time: 19ms

memory: 40332kb

input:

output:

57313311

result:

ok single line: '57313311'

Test #113:

score: 0

Accepted

time: 26ms

memory: 41912kb

input:

output:

412800517

result:

ok single line: '412800517'

Test #114:

score: 0

Accepted

time: 71ms

memory: 58656kb

input:

output:

700780854

result:

ok single line: '700780854'

Test #115:

score: 0

Accepted

time: 37ms

memory: 51528kb

input:

output:

743222193

result:

ok single line: '743222193'

Test #116:

score: 0

Accepted

time: 66ms

memory: 49180kb

input:

output:

348028553

result:

ok single line: '348028553'

Test #117:

score: 0

Accepted

time: 75ms

memory: 70972kb

input:

output:

89020021

result:

ok single line: '89020021'

Test #118:

score: 0

Accepted

time: 19ms

memory: 42064kb

input:

output:

184832304

result:

ok single line: '184832304'

Test #119:

score: 0

Accepted

time: 24ms

memory: 41844kb

input:

output:

774236523

result:

ok single line: '774236523'

Test #120:

score: 0

Accepted

time: 64ms

memory: 58624kb

input:

output:

711005791

result:

ok single line: '711005791'

Test #121:

score: 0

Accepted

time: 40ms

memory: 51540kb

input:

output:

268262891

result:

ok single line: '268262891'

Test #122:

score: 0

Accepted

time: 66ms

memory: 49476kb

input:

output:

913953947

result:

ok single line: '913953947'

Test #123:

score: 0

Accepted

time: 74ms

memory: 71256kb

input:

output:

19609898

result:

ok single line: '19609898'

Test #124:

score: 0

Accepted

time: 23ms

memory: 41948kb

input:

output:

530310194

result:

ok single line: '530310194'

Test #125:

score: 0

Accepted

time: 30ms

memory: 41928kb

input:

output:

111211564

result:

ok single line: '111211564'

Test #126:

score: 0

Accepted

time: 71ms

memory: 58848kb

input:

output:

536050287

result:

ok single line: '536050287'

Test #127:

score: 0

Accepted

time: 40ms

memory: 51600kb

input:

output:

203664810

result:

ok single line: '203664810'

Test #128:

score: 0

Accepted

time: 59ms

memory: 49060kb

input:

output:

464943202

result:

ok single line: '464943202'

Test #129:

score: 0

Accepted

time: 72ms

memory: 71040kb

input:

output:

221495654

result:

ok single line: '221495654'

Test #130:

score: 0

Accepted

time: 18ms

memory: 41864kb

input:

output:

378087212

result:

ok single line: '378087212'

Test #131:

score: 0

Accepted

time: 23ms

memory: 41940kb

input:

output:

984482107

result:

ok single line: '984482107'

Test #132:

score: 0

Accepted

time: 76ms

memory: 58712kb

input:

output:

317476245

result:

ok single line: '317476245'