CSES - Putka Open 2020 – 2/5

Submission details
Task:	Planeetat
Sender:	kluopaja
Submission time:	2020-09-27 18:54:19 +0300
Language:	C++ (C++11)
Status:	READY
Result:	49

Feedback
group	verdict	score
#1	ACCEPTED	24
#2	ACCEPTED	25
#3	RUNTIME ERROR	0

Test results
test	verdict	time	group
#1	ACCEPTED	0.01 s	1, 2, 3	details
#2	ACCEPTED	0.01 s	1, 2, 3	details
#3	ACCEPTED	0.01 s	1, 2, 3	details
#4	ACCEPTED	0.01 s	1, 2, 3	details
#5	ACCEPTED	0.01 s	1, 2, 3	details
#6	ACCEPTED	0.01 s	1, 2, 3	details
#7	ACCEPTED	0.01 s	1, 2, 3	details
#8	ACCEPTED	0.01 s	1, 2, 3	details
#9	ACCEPTED	0.01 s	1, 2, 3	details
#10	ACCEPTED	0.01 s	1, 2, 3	details
#11	ACCEPTED	0.01 s	2, 3	details
#12	ACCEPTED	0.02 s	2, 3	details
#13	ACCEPTED	0.11 s	2, 3	details
#14	RUNTIME ERROR	0.01 s	3	details
#15	RUNTIME ERROR	0.01 s	3	details
#16	RUNTIME ERROR	0.01 s	3	details
#17	RUNTIME ERROR	0.01 s	3	details
#18	RUNTIME ERROR	0.01 s	3	details
#19	RUNTIME ERROR	0.01 s	3	details
#20	RUNTIME ERROR	0.01 s	3	details
#21	RUNTIME ERROR	0.01 s	3	details
#22	RUNTIME ERROR	0.01 s	3	details
#23	RUNTIME ERROR	0.01 s	3	details
#24	RUNTIME ERROR	0.01 s	3	details
#25	RUNTIME ERROR	0.01 s	3	details

Compiler report

input/code.cpp: In function 'void generateGraphs(int, int, int, std::vector<int>&, std::vector<std::vector<int> >&)':
input/code.cpp:63:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(v.size() == tot_nodes) {
      ~~~~~~~~~^~~~~~~~~~~~
input/code.cpp: In function 'int solve(int, int)':
input/code.cpp:83:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < v.size(); ++i) {
                  ~~^~~~~~~~~~
input/code.cpp: In function 'int main()':
input/code.cpp:174:9: warning: unused variable 'comp_1' [-Wunused-variable]
     int comp_1 = 0;
         ^~~~~~

Code

#include <iostream>
#include <cstring>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N_MAX = 5005;
const ll MOD = 1e9+7;
ll fact[N_MAX];
ll pow(ll a, ll b) {
  ll res = 1;
  for(; b; b/=2) {
    if(b&1) {
      res = res * a % MOD;;
    }
    a = a * a % MOD;
  }
  return res;
}
ll nCk(ll n, ll k) {
  if(k > n) return 0;
  ll tmp = fact[k] * fact[n-k] % MOD;
  return fact[n] * pow(tmp, MOD-2) % MOD;
}
int find(int a, vector<int>& du) {
  if(du[a] == a) return a;
  return du[a] = find(du[a], du);
}
void merge(int a, int b, vector<int>& du) {
  du[find(a, du)] = find(b, du);
}
bool is_tree(vector<int> v) {
  vector<int> du(v.size());
  for(size_t i = 0; i < v.size(); ++i) du[i] = i;
  for(size_t i = 0; i < v.size(); ++i) {
    merge(i, v[i], du);
  }
  int mi = 1e9;
  int ma = -1e9;
  for(size_t i = 0; i < v.size(); ++i) {
    int x = find(v[i], du);
    mi = min(mi, x);
    ma = max(ma, x);
  }
  return mi == ma;
}
int countComponents(vector<int> v) {
  vector<int> du(v.size());
  for(size_t i = 0; i < v.size(); ++i) du[i] = i;
  for(size_t i = 0; i < v.size(); ++i) {
    if(v[i] == -1) continue;
    merge(i, v[i], du);
  }
  for(size_t i = 0; i < v.size(); ++i) {
    find(i, du);
  }
  sort(du.begin(), du.end());
  du.erase(unique(du.begin(), du.end()), du.end());
  return du.size();
}
void generateGraphs(int tot_nodes, int tot_edges, int n_edges, vector<int>& v, vector<vector<int> >& out) {
  if(v.size() == tot_nodes) {
    if(n_edges == tot_edges) {
      out.push_back(v);
    }
    return;
  }
  v.push_back(-1);
  generateGraphs(tot_nodes, tot_edges, n_edges, v, out);
  v.pop_back();
  for(int i = 0; i < tot_nodes; ++i) {
    v.push_back(i);
    generateGraphs(tot_nodes, tot_edges, n_edges+1, v, out);
    v.pop_back();
  }
}
int solve(int n, int k) {
  vector<int> tmp;
  vector<vector<int> > v;
  generateGraphs(n, n, 0, tmp, v);
  int ans = 0;
  for(int i = 0; i < v.size(); ++i) {
    if(countComponents(v[i]) == k) ++ans;
  }
  return ans;
}
ll g_dp[101][101];
ll g(ll n, ll r) {
  if(g_dp[n][r] != -1) return g_dp[n][r];
  if(n == 0) return 1;
  ll sum = 0;
  for(int i = 1; i <= n; ++i) {
    ll i_trees = pow(i, i-1);
    // always take the smallest
    ll i_select = nCk(n-1, i-1);
    sum += r*g(n-i, r)%MOD * i_trees%MOD * i_select%MOD;
  }
  return g_dp[n][r] = sum%MOD;
}
ll lt_dp2[101][101];
ll loopTrees(int n, int r) {
  if(lt_dp2[n][r] != -1) return lt_dp2[n][r];
  ll tmp = nCk(n, r)*fact[r-1]%MOD;
  return lt_dp2[n][r] = tmp*g(n-r, r)%MOD;
}
ll lt_dp[101];
ll loopTrees(int n) {
  if(lt_dp[n] != -1) return lt_dp[n];
  ll sum = 0;
  for(int i = 1; i <= n; ++i) {
    sum += loopTrees(n, i);
  }
  return lt_dp[n] = sum%MOD;
}
ll dp[101][101];
void solve2(int n) {
  for(int i = 0; i <= n; ++i) {
    for(int j = 0; j <= n; ++j) {
      dp[i][j] = 0;
    }
  }
  dp[0][0] = 1;
  for(int i = 1; i <= n; ++i) {
    for(int j = 1; j <= i; ++j) {
      for(int k = 1; k <= i; ++k) {
        dp[i][j] += dp[i-k][j-1] * nCk(i-1, k-1) % MOD * loopTrees(k) % MOD;
      }
      dp[i][j] %= MOD;
    }
  }
  for(int i = 1; i <= n; ++i) {
    cout<<dp[n][i]<<'\n';
  }
}
int main() {
  memset(lt_dp, -1, sizeof(lt_dp));
  memset(lt_dp2, -1, sizeof(lt_dp2));
  memset(g_dp, -1, sizeof(g_dp));
  fact[0] = 1;
  for(int i = 1; i < N_MAX; ++i) {
    fact[i] = fact[i-1] * i % MOD;
  }
  //cout<<loopTrees(3, 1)<<endl;
  //return 0;
  int n;
  cin>>n;
  solve2(n);
  return 0;
  for(int i = 1; i < 7; ++i) {
    for(int j = 1; j <= i; ++j) {
      cout<<setw(10)<<solve(i, j);
    }
    cout<<endl;
  }
  for(int i = 1; i < 7; ++i) {
    /*
    cout<<"i: " <<i<<endl;
    for(int j = 1; j <= i; ++j) {
      cout<<loopTrees(i, j)<<' ';
    }
    cout<<endl;
    */
    cout<<i<<' '<<loopTrees(i)<<endl;
  }
  return 0;
  for(int n = 1; n < 10; ++n) {
    vector<int> tmp;
    vector<vector<int> > v;
    generateGraphs(n, n, 0, tmp, v);
    vector<vector<int> > v2;
    generateGraphs(n, n-1, 0, tmp, v2);
    int n_trees = 0;
    int comp_1 = 0;
    for(size_t i = 0; i < v.size(); ++i) {
      int components = countComponents(v[i]);
      n_trees += (components == 2);
    }
    int n_trees_2 = 0;
    for(size_t i = 0; i < v2.size(); ++i) {
      int components = countComponents(v2[i]);
      n_trees_2 += (components == 1);
    }
    cout<<n<<' '<<n_trees<<' '<<n_trees_2<<endl;
  }
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
`1` view save

correct output
`1` view save

user output
`1` view save

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
`2` view save

correct output
`3 1` view save

user output
`3 1` view save

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
`3` view save

correct output
`17 9 1` view save

user output
`17 9 1` view save

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
`4` view save

correct output
`142 95 18 1` view save

user output
`142 95 18 1` view save

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
`5` view save

correct output
`1569 1220 305 30 1` view save

user output
`1569 1220 305 30 1` view save

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
`6` view save

correct output
`21576 18694 5595 745 45 ...` view save

user output
`21576 18694 5595 745 45 ...` view save

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

input
`7` view save

correct output
`355081 334369 113974 18515 1540 ...` view save

user output
`355081 334369 113974 18515 1540 ...` view save

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

input
`8` view save

correct output
`6805296 6852460 2581964 484729 49840 ...` view save

user output
`6805296 6852460 2581964 484729 49840 ...` view save

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

input
`9` view save

correct output
`148869153 158479488 64727522 13591116 1632099 ...` view save

user output
`148869153 158479488 64727522 13591116 1632099 ...` view save

Test 10

Group: 1, 2, 3

Verdict: ACCEPTED

input
`10` view save

correct output
`660215659 85349908 783995053 409987640 55545735 ...` view save

user output
`660215659 85349908 783995053 409987640 55545735 ...` view save

Test 11

Group: 2, 3

Verdict: ACCEPTED

input
`20` view save

correct output
`8033007 474885151 998010619 720259168 345757330 ...` view save

user output
`8033007 474885151 998010619 720259168 345757330 ...` Truncated

Test 12

Group: 2, 3

Verdict: ACCEPTED

input
`50` view save

correct output
`637699856 613177596 194234103 50828885 988168359 ...` view save

user output
`637699856 613177596 194234103 50828885 988168359 ...` Truncated

Test 13

Group: 2, 3

Verdict: ACCEPTED

input
`100` view save

correct output
`894456323 406549429 962038245 430640330 61348310 ...` view save

user output
`894456323 406549429 962038245 430640330 61348310 ...` Truncated

Test 14

Group: 3

Verdict: RUNTIME ERROR

input
`666` view save

correct output
`189730587 968711879 553374698 53051125 139917248 ...` view save

user output
(empty)

Test 15

Group: 3

Verdict: RUNTIME ERROR

input
`3333` view save

correct output
`79235821 455292218 627100211 591681254 695866885 ...` view save

user output
(empty)

Test 16

Group: 3

Verdict: RUNTIME ERROR

input
`4991` view save

correct output
`482116496 245260697 151422537 180441123 318466624 ...` view save

user output
(empty)

Test 17

Group: 3

Verdict: RUNTIME ERROR

input
`4992` view save

correct output
`141010647 787351178 684701591 872974815 631476284 ...` view save

user output
(empty)

Test 18

Group: 3

Verdict: RUNTIME ERROR

input
`4993` view save

correct output
`504034249 588971460 281533415 928250892 416697844 ...` view save

user output
(empty)

Test 19

Group: 3

Verdict: RUNTIME ERROR

input
`4994` view save

correct output
`266134603 90079109 544661648 812099750 17249410 ...` view save

user output
(empty)

Test 20

Group: 3

Verdict: RUNTIME ERROR

input
`4995` view save

correct output
`833898560 663839791 109127071 321675160 86285359 ...` view save

user output
(empty)

Test 21

Group: 3

Verdict: RUNTIME ERROR

input
`4996` view save

correct output
`721158645 167929822 115103278 491345159 114397872 ...` view save

user output
(empty)

Test 22

Group: 3

Verdict: RUNTIME ERROR

input
`4997` view save

correct output
`691405606 436947443 82656395 514529009 783319673 ...` view save

user output
(empty)

Test 23

Group: 3

Verdict: RUNTIME ERROR

input
`4998` view save

correct output
`829675470 688714502 189351950 956110193 20883331 ...` view save

user output
(empty)

Test 24

Group: 3

Verdict: RUNTIME ERROR

input
`4999` view save

correct output
`343936737 47032567 190931571 827280581 160866637 ...` view save

user output
(empty)

Test 25

Group: 3

Verdict: RUNTIME ERROR

input
`5000` view save

correct output
`364064601 633559852 352848841 666954216 428009512 ...` view save

user output
(empty)

Putka Open 2020 – 2/5

Planeetat

Compiler report

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Tasks

Submissions (kluopaja)