QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#569061 | #8339. Rooted Tree | ayxrakzil | TL | 142ms | 9640kb | C++14 | 1.1kb | 2024-09-16 20:16:10 | 2024-09-16 20:16:11 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
const ll K = 1e7 + 5, mod = 1e9 + 9;
ll m, k, f[K], ans;
ll read() {
ll res = 0, i = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') i = -i;
c = getchar();
}
while (c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
return res * i;
}
void write(ll x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
ll qpow(ll a, ll b) {
ll res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
int main() {
m = read(), k = read();
for (ll i = 1; i <= k; ++i)
f[i] = (((f[i - 1] + (m - 1) * f[i - 1] % mod * qpow(((m - 1) * (i - 1) % mod + 1) % mod, mod - 2) % mod) % mod + m) % mod) % mod;
for (ll i = 1; i <= k; ++i)
ans = (ans + (m * f[i - 1] % mod * qpow(((m - 1) * (i - 1) % mod + 1) % mod, mod - 2) + m) % mod) % mod;
write(ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3736kb
input:
6 2
output:
18
result:
ok 1 number(s): "18"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
2 6
output:
600000038
result:
ok 1 number(s): "600000038"
Test #3:
score: 0
Accepted
time: 142ms
memory: 9640kb
input:
83 613210
output:
424200026
result:
ok 1 number(s): "424200026"
Test #4:
score: -100
Time Limit Exceeded
input:
48 6713156
output:
198541581