CSES - Putka Open 2020 – 2/5 - Results
Submission details
Task:Planeetat
Sender:kluopaja
Submission time:2020-09-27 18:54:19 +0300
Language:C++ (C++11)
Status:READY
Result:49
Feedback
groupverdictscore
#1ACCEPTED24
#2ACCEPTED25
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.01 s1, 2, 3details
#3ACCEPTED0.01 s1, 2, 3details
#4ACCEPTED0.01 s1, 2, 3details
#5ACCEPTED0.01 s1, 2, 3details
#6ACCEPTED0.01 s1, 2, 3details
#7ACCEPTED0.01 s1, 2, 3details
#8ACCEPTED0.01 s1, 2, 3details
#9ACCEPTED0.01 s1, 2, 3details
#10ACCEPTED0.01 s1, 2, 3details
#11ACCEPTED0.01 s2, 3details
#12ACCEPTED0.02 s2, 3details
#13ACCEPTED0.11 s2, 3details
#140.01 s3details
#150.01 s3details
#160.01 s3details
#170.01 s3details
#180.01 s3details
#190.01 s3details
#200.01 s3details
#210.01 s3details
#220.01 s3details
#230.01 s3details
#240.01 s3details
#250.01 s3details

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

correct output
1

user output
1

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
2

correct output
3
1

user output
3
1

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
3

correct output
17
9
1

user output
17
9
1

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
4

correct output
142
95
18
1

user output
142
95
18
1

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
5

correct output
1569
1220
305
30
1

user output
1569
1220
305
30
1

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
6

correct output
21576
18694
5595
745
45
...

user output
21576
18694
5595
745
45
...

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

input
7

correct output
355081
334369
113974
18515
1540
...

user output
355081
334369
113974
18515
1540
...

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

input
8

correct output
6805296
6852460
2581964
484729
49840
...

user output
6805296
6852460
2581964
484729
49840
...

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

input
9

correct output
148869153
158479488
64727522
13591116
1632099
...

user output
148869153
158479488
64727522
13591116
1632099
...

Test 10

Group: 1, 2, 3

Verdict: ACCEPTED

input
10

correct output
660215659
85349908
783995053
409987640
55545735
...

user output
660215659
85349908
783995053
409987640
55545735
...

Test 11

Group: 2, 3

Verdict: ACCEPTED

input
20

correct output
8033007
474885151
998010619
720259168
345757330
...

user output
8033007
474885151
998010619
720259168
345757330
...
Truncated

Test 12

Group: 2, 3

Verdict: ACCEPTED

input
50

correct output
637699856
613177596
194234103
50828885
988168359
...

user output
637699856
613177596
194234103
50828885
988168359
...
Truncated

Test 13

Group: 2, 3

Verdict: ACCEPTED

input
100

correct output
894456323
406549429
962038245
430640330
61348310
...

user output
894456323
406549429
962038245
430640330
61348310
...
Truncated

Test 14

Group: 3

Verdict:

input
666

correct output
189730587
968711879
553374698
53051125
139917248
...

user output
(empty)

Test 15

Group: 3

Verdict:

input
3333

correct output
79235821
455292218
627100211
591681254
695866885
...

user output
(empty)

Test 16

Group: 3

Verdict:

input
4991

correct output
482116496
245260697
151422537
180441123
318466624
...

user output
(empty)

Test 17

Group: 3

Verdict:

input
4992

correct output
141010647
787351178
684701591
872974815
631476284
...

user output
(empty)

Test 18

Group: 3

Verdict:

input
4993

correct output
504034249
588971460
281533415
928250892
416697844
...

user output
(empty)

Test 19

Group: 3

Verdict:

input
4994

correct output
266134603
90079109
544661648
812099750
17249410
...

user output
(empty)

Test 20

Group: 3

Verdict:

input
4995

correct output
833898560
663839791
109127071
321675160
86285359
...

user output
(empty)

Test 21

Group: 3

Verdict:

input
4996

correct output
721158645
167929822
115103278
491345159
114397872
...

user output
(empty)

Test 22

Group: 3

Verdict:

input
4997

correct output
691405606
436947443
82656395
514529009
783319673
...

user output
(empty)

Test 23

Group: 3

Verdict:

input
4998

correct output
829675470
688714502
189351950
956110193
20883331
...

user output
(empty)

Test 24

Group: 3

Verdict:

input
4999

correct output
343936737
47032567
190931571
827280581
160866637
...

user output
(empty)

Test 25

Group: 3

Verdict:

input
5000

correct output
364064601
633559852
352848841
666954216
428009512
...

user output
(empty)