oj.uz

Submission #722968

# Submission time Handle Problem Language Result Execution time Memory
722968 2023-04-13T06:34:17 Z loctildore Bi-ing Lottery Treekets (CCO22_day2problem1) C++14
0 / 25
 51 ms 33512 KB 
#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 balls[4069];
int lft[4069], rht[4069], dir[4069];
ll fact[4069];
bool done[4069][4069][2];
ll dp[4069][4069][2];
ll expo(ll x, int c) {
    if (c == 1) {
        return x;
    }
    ll tmp = expo(x, c/2);
    tmp = (tmp * tmp) % MOD;
    return (tmp * (c % 1 ? x : 1)) % MOD;
}
ll chs(int x, int y) {
    ll rtn = fact[x];
    rtn = (rtn * expo(fact[y], MOD - 2)) % MOD;
    rtn = (rtn * expo(fact[x - y], MOD - 2)) % MOD;
    return rtn;
}
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, bool p = false) {
    if (x == 0) return carry == 0;
    if (done[x][carry][p]) return dp[x][carry][p];
    done[x][carry][p] = true;
    int tmpb = balls[x] - p;
    if (tmpb < 0) {
        if (carry == 0) return dp[x][carry][p] = 0;
        tmpb++;carry--;
    }
    for (int i = 0; i <= tmpb; i++) {
        ll tmp;
        if (dir[i]) {
            tmp = (fnd(lft[x], tmpb - i, p) * fnd(rht[x], carry + i, p)) % MOD;
        }
        else {
            tmp = (fnd(lft[x], carry + i, p) * fnd(rht[x], tmpb - i, p)) % MOD;
        }
        tmp = (tmp * perm(tmpb, tmpb - i)) % MOD;
        tmp = (tmp * perm(carry + i, i)) % MOD;
        dp[x][carry][p] = (dp[x][carry][p] + tmp) % MOD;
    }
    if (!p) dp[x][carry][p] = (dp[x][carry][p] + fnd(x, carry, true)) % MOD;
    //cout<<x<<' '<<carry<<' '<<p<<':'<<dp[x][carry][p]<<endl;
    return dp[x][carry][p];
}
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;
    }
    cout<<fnd(1, 0)<<endl;
    return 0;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 33484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 33356 KB Output is correct
2 Correct 30 ms 33488 KB Output is correct
3 Correct 51 ms 33512 KB Output is correct
4 Incorrect 32 ms 33016 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -