CSES - Putka Open 2020 – 2/5 - Results
Submission details
Task:Planeetat
Sender:hltk
Submission time:2020-09-27 17:17:11 +0300
Language:C++ (C++17)
Status:READY
Result:49
Feedback
groupverdictscore
#1ACCEPTED24
#2ACCEPTED25
#30
Test results
testverdicttimegroup
#1ACCEPTED0.03 s1, 2, 3details
#2ACCEPTED0.03 s1, 2, 3details
#3ACCEPTED0.02 s1, 2, 3details
#4ACCEPTED0.02 s1, 2, 3details
#5ACCEPTED0.03 s1, 2, 3details
#6ACCEPTED0.02 s1, 2, 3details
#7ACCEPTED0.03 s1, 2, 3details
#8ACCEPTED0.03 s1, 2, 3details
#9ACCEPTED0.02 s1, 2, 3details
#10ACCEPTED0.02 s1, 2, 3details
#11ACCEPTED0.02 s2, 3details
#12ACCEPTED0.03 s2, 3details
#13ACCEPTED0.03 s2, 3details
#14--3details
#15--3details
#16--3details
#17--3details
#18--3details
#19--3details
#20--3details
#21--3details
#22--3details
#23--3details
#24--3details
#25--3details

Code

#include <functional>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
template <typename T> T pow(T a, ll b) {
T r = 1;
for (; b; b /= 2, a *= a)
if (b % 2) r *= a;
return r;
}
// source: ecnerwala, own, benq
template <int MOD> struct modint {
int v;
modint() : v(0) {}
modint(ll x) : v(x % MOD) {
if (v < 0) v += MOD;
}
explicit operator int() const { return v; }
explicit operator ll() const { return v; }
friend ostream &operator<<(ostream &out, const modint &a) {
return out << int(a);
}
friend istream &operator>>(istream &in, modint &a) {
ll x;
in >> x;
a = modint(x);
return in;
}
// only works if MOD is prime
modint inv() const {
return pow(*this, MOD - 2);
}
friend modint inv(const modint &x) { return x.inv(); }
modint &operator+=(const modint &a) {
v += a.v;
if (v >= MOD) v -= MOD;
return *this;
}
modint &operator-=(const modint &a) {
v -= a.v;
if (v < 0) v += MOD;
return *this;
}
modint &operator*=(const modint &a) {
v = ll(v) * ll(a.v) % MOD;
return *this;
}
modint &operator/=(const modint &a) { return *this *= a.inv(); }
friend modint operator+(const modint &a, const modint &b) {
return modint(a) += b;
}
friend modint operator-(const modint &a, const modint &b) {
return modint(a) -= b;
}
friend modint operator*(const modint &a, const modint &b) {
return modint(a) *= b;
}
friend modint operator/(const modint &a, const modint &b) {
return modint(a) /= b;
}
};
constexpr ll MOD = 1000000007;
using mint = modint<MOD>;
namespace nCr {
vector<mint> fact, ifact;
void init(int N = int(1e6)) {
fact.resize(N + 1);
ifact.resize(N + 1);
fact[0] = 1;
for (int i = 1; i <= N; ++i)
fact[i] = fact[i - 1] * i;
ifact[N] = 1 / fact[N];
for (int i = N; i > 0; --i)
ifact[i - 1] = i * ifact[i];
}
mint choose(int a, int b) {
if (a < b || b < 0) return 0;
return fact[a] * ifact[b] * ifact[a - b];
}
}
int main() {
nCr::init();
int n;
cin >> n;
vector<mint> p(n + 1);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= i; ++j)
p[i] += nCr::choose(i, j) * pow(mint(i - j), i - j) * pow(mint(j), j);
for (int i = 1; i <= n; ++i)
p[i] /= i;
vector<vector<mint>> t(n + 1, vector<mint>(n + 1));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
t[i][j] = pow(p[i] * nCr::ifact[i], j) * nCr::ifact[j];
vector<vector<mint>> dp(n + 1, vector<mint>(n + 1));
dp[0][0] = 1;
for (int i = 1; i <= n; ++i)
for (int k = n; k >= i; --k)
for (int j = 1; k - i * j >= 0; ++j)
for (int z = j; z <= n; ++z)
dp[k][z] += dp[k - i * j][z - j] * t[i][j];
for (int i = 1; i <= n; ++i)
cout << dp[n][i] * nCr::fact[n] << '\n';
}

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)