Submission #723061

#	Time	Username	Problem	Language	Result	Execution time	Memory
723061		loctildore	Bi-ing Lottery Treekets (CCO22_day2problem1)	C++14	12 / 25	1070 ms	43268 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define endl '\n'
#define all(x) begin(x), end(x)
#define MOD 1000000007
int n, k;
int sz[4069];
int balls[4069];
int lft[4069], rht[4069], dir[4069];
ll fact[4069];
bool done[4069][4069];
ll dp[4069][4069];
int calsz(int x) {
    if (!x) return 0;
    return sz[x] = calsz(lft[x]) + calsz(rht[x]) + 1 - balls[x];
}
ll expo(ll x, int c) {
    if (c == 1) {
        return x;
    }
    ll tmp = expo(x, c/2);
    tmp = (tmp * tmp) % MOD;
    return (tmp * (c % 2 ? x : 1)) % MOD;
}
ll perm(int x, int y) {
    ll rtn = fact[x];
    rtn = (rtn * expo(fact[x - y], MOD - 2)) % MOD;
    return rtn;
}
ll fnd(int x, int carry) {
    if (x == 0) return carry == 0;
    if (done[x][carry]) return dp[x][carry];
    done[x][carry] = true;
    if (carry > sz[x]) return dp[x][carry] = 0;
    if (carry == sz[x]) {
        ll tmp = (fnd(lft[x], sz[lft[x]]) * fnd(rht[x], sz[rht[x]])) % MOD;
        tmp = (tmp * perm(carry + balls[x], balls[x])) % MOD;
        return dp[x][carry] = tmp;
    }
    if (dir[x] && balls[x] + carry >= sz[rht[x]]) {
        ll tmp = (fnd(lft[x], balls[x] + carry - sz[rht[x]]) * fnd(rht[x], sz[rht[x]])) % MOD;
        tmp = (tmp * perm(carry + balls[x], balls[x])) % MOD;
        dp[x][carry] = (dp[x][carry] + tmp) % MOD;
    }
    if (!dir[x] && balls[x] + carry >= sz[lft[x]]) {
        ll tmp = (fnd(lft[x], sz[lft[x]]) * fnd(rht[x], balls[x] + carry - sz[lft[x]])) % MOD;
        tmp = (tmp * perm(carry + balls[x], balls[x])) % MOD;
        dp[x][carry] = (dp[x][carry] + tmp) % MOD;
    }
    for (int i = 0; i <= balls[x]; i++) {
        ll tmp;
        if (dir[x]) {
            if (sz[rht[x]] <= carry + i) continue;
            tmp = (fnd(lft[x], balls[x] - i) * fnd(rht[x], carry + i)) % MOD;
        }
        else {
            if (sz[lft[x]] <= carry + i) continue;
            tmp = (fnd(lft[x], carry + i) * fnd(rht[x], balls[x] - i)) % MOD;
        }
        tmp = (tmp * perm(balls[x], balls[x] - i)) % MOD;
        tmp = (tmp * perm(carry + i, i)) % MOD;
        dp[x][carry] = (dp[x][carry] + tmp) % MOD;
    }
    //cout<<x<<' '<<carry<<'?'<<sz[x]<<':'<<dp[x][carry]<<endl;
    return dp[x][carry];
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cin>>n>>k;
    fact[0] = 1;
    for (int i = 1; i < 4069; i++) {
        fact[i] = (fact[i-1] * i) % MOD;
    }
    for (int i = 0; i < k; i++) {
        int a;
        cin>>a;
        balls[a]++;
    }
    for (int i = 1; i <= n; i++) {
        cin>>lft[i]>>rht[i];
        dir[rht[i]] = true;
    }
    calsz(1);
    cout<<fnd(1, 0)<<endl;
    return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 0 / 4
• Subtask 3: 9 / 9
• Subtask 4: 0 / 9