Submission #1108784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108784		TrungDuy3107	Bi-ing Lottery Treekets (CCO22_day2problem1)	C++14	4 / 25	47 ms	126288 KiB

Main

#include<bits/stdc++.h>
using namespace std;

#define maxn 4'007
#define MOD 1'000'000'007
#define int long long
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],0LL);
//  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
• Subtask 2: 4 / 4
• Subtask 3: 0 / 9
• Subtask 4: 0 / 9