This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |