Task: | Planeetat |
Sender: | hltk |
Submission time: | 2020-09-27 17:17:11 +0300 |
Language: | C++ (C++17) |
Status: | READY |
Result: | 49 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 24 |
#2 | ACCEPTED | 25 |
#3 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.03 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.03 s | 1, 2, 3 | details |
#3 | ACCEPTED | 0.02 s | 1, 2, 3 | details |
#4 | ACCEPTED | 0.02 s | 1, 2, 3 | details |
#5 | ACCEPTED | 0.03 s | 1, 2, 3 | details |
#6 | ACCEPTED | 0.02 s | 1, 2, 3 | details |
#7 | ACCEPTED | 0.03 s | 1, 2, 3 | details |
#8 | ACCEPTED | 0.03 s | 1, 2, 3 | details |
#9 | ACCEPTED | 0.02 s | 1, 2, 3 | details |
#10 | ACCEPTED | 0.02 s | 1, 2, 3 | details |
#11 | ACCEPTED | 0.02 s | 2, 3 | details |
#12 | ACCEPTED | 0.03 s | 2, 3 | details |
#13 | ACCEPTED | 0.03 s | 2, 3 | details |
#14 | TIME LIMIT EXCEEDED | -- | 3 | details |
#15 | TIME LIMIT EXCEEDED | -- | 3 | details |
#16 | TIME LIMIT EXCEEDED | -- | 3 | details |
#17 | TIME LIMIT EXCEEDED | -- | 3 | details |
#18 | TIME LIMIT EXCEEDED | -- | 3 | details |
#19 | TIME LIMIT EXCEEDED | -- | 3 | details |
#20 | TIME LIMIT EXCEEDED | -- | 3 | details |
#21 | TIME LIMIT EXCEEDED | -- | 3 | details |
#22 | TIME LIMIT EXCEEDED | -- | 3 | details |
#23 | TIME LIMIT EXCEEDED | -- | 3 | details |
#24 | TIME LIMIT EXCEEDED | -- | 3 | details |
#25 | TIME LIMIT EXCEEDED | -- | 3 | details |
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, benqtemplate <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 primemodint 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: TIME LIMIT EXCEEDED
input |
---|
666 |
correct output |
---|
189730587 968711879 553374698 53051125 139917248 ... |
user output |
---|
(empty) |
Test 15
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
3333 |
correct output |
---|
79235821 455292218 627100211 591681254 695866885 ... |
user output |
---|
(empty) |
Test 16
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
4991 |
correct output |
---|
482116496 245260697 151422537 180441123 318466624 ... |
user output |
---|
(empty) |
Test 17
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
4992 |
correct output |
---|
141010647 787351178 684701591 872974815 631476284 ... |
user output |
---|
(empty) |
Test 18
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
4993 |
correct output |
---|
504034249 588971460 281533415 928250892 416697844 ... |
user output |
---|
(empty) |
Test 19
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
4994 |
correct output |
---|
266134603 90079109 544661648 812099750 17249410 ... |
user output |
---|
(empty) |
Test 20
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
4995 |
correct output |
---|
833898560 663839791 109127071 321675160 86285359 ... |
user output |
---|
(empty) |
Test 21
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
4996 |
correct output |
---|
721158645 167929822 115103278 491345159 114397872 ... |
user output |
---|
(empty) |
Test 22
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
4997 |
correct output |
---|
691405606 436947443 82656395 514529009 783319673 ... |
user output |
---|
(empty) |
Test 23
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
4998 |
correct output |
---|
829675470 688714502 189351950 956110193 20883331 ... |
user output |
---|
(empty) |
Test 24
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
4999 |
correct output |
---|
343936737 47032567 190931571 827280581 160866637 ... |
user output |
---|
(empty) |
Test 25
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
5000 |
correct output |
---|
364064601 633559852 352848841 666954216 428009512 ... |
user output |
---|
(empty) |