Submission #722968

#TimeUsernameProblemLanguageResultExecution timeMemory
722968loctildoreBi-ing Lottery Treekets (CCO22_day2problem1)C++14
0 / 25
51 ms33512 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...