Submission #1108783

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1108783	2024-11-05T04:57:12 Z	TrungDuy3107	Bi-ing Lottery Treekets (CCO22_day2problem1)	C++14	Compilation error	0 ms	0 KB

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],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;
}

Compilation message

Main.cpp: In function 'void dfs(long long int)':
Main.cpp:49:31: error: no matching function for call to 'max(long long int, int)'
   49 |   len[u] = max(len[u]-cnt[u],0);
      |                               ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
Main.cpp:49:31: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   49 |   len[u] = max(len[u]-cnt[u],0);
      |                               ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
Main.cpp:49:31: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   49 |   len[u] = max(len[u]-cnt[u],0);
      |                               ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
Main.cpp:49:31: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   49 |   len[u] = max(len[u]-cnt[u],0);
      |                               ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
Main.cpp:49:31: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   49 |   len[u] = max(len[u]-cnt[u],0);
      |                               ^