oj.uz

Submission #1108782

# Submission time Handle Problem Language Result Execution time Memory
1108782 2024-11-05T04:13:05 Z TrungDuy3107 Bi-ing Lottery Treekets (CCO22_day2problem1) C++14
4 / 25
 46 ms 63312 KB 
#include<bits/stdc++.h>
using namespace std;

#define maxn 4'007
#define MOD 1'000'000'007
typedef long long LL;
int fact[maxn], invF[maxn];
int power(int a, int n)
{
  int res = 1;
  for(;n;n>>=1,a=1LL*a*a%MOD)
    if(n&1) res = 1LL*res*a%MOD;
  return res;
}
int n;
vector<int> g[maxn];
int cnt[maxn];
int dp[maxn][maxn];
int len[maxn];
int tmp[maxn];

void dfs(int u)
{
  len[u] = 1;
  if(g[u].size() == 0) dp[u][0] = 1;
  if(g[u].size() == 1) {
    dfs(g[u][0]);
    for(int i=0;i<=len[g[u][0]];i++) dp[u][i] = dp[g[u][0]][i];
    len[u] += len[g[u][0]];
  }
  if(g[u].size() == 2) {
    int a = g[u][0], b = g[u][1];
    dfs(a);dfs(b);
    for(int i=0;i<=len[a];i++)
      for(int j=0;j<=len[b];j++) {
        dp[u][i+j] += 1LL*dp[a][i]*dp[b][j]%MOD;
        if(dp[u][i+j] >= MOD) dp[u][i+j] -= MOD;
      }
    len[u] += len[a]+len[b];
  }
  dp[u][len[u]] = dp[u][len[u]-1];
  for(int i=0;i<=len[u]-cnt[u];i++) {
    dp[u][i] = 1LL*dp[u][i+cnt[u]]*fact[i+cnt[u]]%MOD*invF[i]%MOD;
  }
  if(cnt[u] > len[u]) {
    for(int i=0;i<=len[u];i++) dp[u][i] = 0;
  }
  len[u] = max(len[u]-cnt[u],0);
//  cout << u << '\n';
//  for(int i=0;i<=len[u];i++) cout << dp[u][i] << ' ';cout << '\n';
}
int32_t main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);

  int k;
  cin >> n >> k;
  fact[0] = 1;
  for(int i=1;i<=n;i++) fact[i] = 1LL*fact[i-1]*i%MOD;
  invF[n] = power(fact[n], MOD-2);
  for(int i=n-1;i>=0;i--) invF[i] = 1LL*invF[i+1]*(i+1)%MOD;
  for(int i=1;i<=k;i++) {
    int input;
    cin >> input;
    cnt[input]++;
  }
  for(int i=1;i<=n;i++) {
    int u, v;
    cin >> u >> v;
    if(u) g[i].push_back(u);
    if(v) g[i].push_back(v);
  }
  dfs(1);
  cout << dp[1][0];
  return 0;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 2808 KB Output is correct
6 Incorrect 1 ms 2640 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 63312 KB Output is correct
2 Correct 26 ms 63056 KB Output is correct
3 Correct 6 ms 35832 KB Output is correct
4 Correct 10 ms 62840 KB Output is correct
5 Correct 10 ms 62800 KB Output is correct
6 Correct 9 ms 62800 KB Output is correct
7 Correct 15 ms 63224 KB Output is correct
8 Correct 10 ms 62800 KB Output is correct
9 Correct 14 ms 62800 KB Output is correct
10 Correct 46 ms 63312 KB Output is correct
11 Correct 34 ms 63312 KB Output is correct
12 Correct 5 ms 31568 KB Output is correct
13 Correct 32 ms 60756 KB Output is correct
14 Correct 23 ms 58448 KB Output is correct
15 Correct 8 ms 56400 KB Output is correct
16 Correct 40 ms 62544 KB Output is correct
17 Correct 29 ms 58460 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 45648 KB Output is correct
2 Correct 11 ms 62968 KB Output is correct
3 Correct 9 ms 53328 KB Output is correct
4 Incorrect 12 ms 53320 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 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 2808 KB Output is correct
6 Incorrect 1 ms 2640 KB Output isn't correct
7 Halted 0 ms 0 KB -