QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#639480 | #8339. Rooted Tree | Blamek# | TL | 1443ms | 3708kb | C++17 | 818b | 2024-10-13 19:52:43 | 2024-10-13 19:52:51 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 9;
int qmi(int a, int b = mod - 2) {
int ans = 1;
if (b == 0) return ans;
if (b & 1) ans = a;
return ans * qmi(a * a % mod, b >> 1) % mod;
}
void solve() {
int m, k;
cin >> m >> k;
int ans = 0, res = 0, sum = 1;
for (int i = 1; i <= k; i++) {
int z = (res * qmi(sum) % mod + 1) % mod;
ans = (ans + z * m % mod) % mod;
sum = sum + m - 1;
res -= z - 1;
res += z * m;
res = (res % mod + mod) % mod;
// cout<<ans<<" "<<res<<" "<<sum<<"\n";
}
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3644kb
input:
6 2
output:
18
result:
ok 1 number(s): "18"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
2 6
output:
600000038
result:
ok 1 number(s): "600000038"
Test #3:
score: 0
Accepted
time: 132ms
memory: 3588kb
input:
83 613210
output:
424200026
result:
ok 1 number(s): "424200026"
Test #4:
score: 0
Accepted
time: 1443ms
memory: 3620kb
input:
48 6713156
output:
198541581
result:
ok 1 number(s): "198541581"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
1 111
output:
6216
result:
ok 1 number(s): "6216"
Test #6:
score: -100
Time Limit Exceeded
input:
28 7304152
output:
457266679