Submission #723070

#	Time	Username	Problem	Language	Result	Execution time	Memory
723070		loctildore	Bi-ing Lottery Treekets (CCO22_day2problem1)	C++14	25 / 25	257 ms	129100 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 perm[4069][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 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;
    for (int i = 0; i < 4069; i++) {
        perm[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            perm[i][j] = (perm[i-1][j-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: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9