QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#685398 | #8339. Rooted Tree | ucup-team1412 | TL | 1492ms | 111524kb | C++23 | 879b | 2024-10-28 19:15:44 | 2024-10-28 19:15:44 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const ll maxn = 1e7 + 10;
const ll maxm = 1e7 + 10;
const ll inf = 0x3f3f3f3f;
const ll P = 1e9 + 9;
ll quickpow(ll x, ll y) {
ll ans = 1;
while (y) {
if (y & 1) ans *= x;
ans %= P;
y >>= 1;
x *= x;
x %= P;
}
return ans % P;
}
ll A[maxn], B[maxn];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll m, k;
cin >> m >> k;
A[0] = 0;
B[0] = 0;
// cout << quickpow(3, 5);
for (ll i = 1; i <= k; i++) {
A[i] = (A[i - 1] * ((m - 1) * quickpow((m - 1) * (i - 1) + 1, P - 2) % P + 1) % P + m % P) % P;
B[i] = (B[i - 1] + A[i - 1] * quickpow((m - 1) * (i - 1) + 1, P - 2) % P) % P;
}
cout << (A[k] + B[k]) % P;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 5680kb
input:
6 2
output:
18
result:
ok 1 number(s): "18"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5616kb
input:
2 6
output:
600000038
result:
ok 1 number(s): "600000038"
Test #3:
score: 0
Accepted
time: 136ms
memory: 15220kb
input:
83 613210
output:
424200026
result:
ok 1 number(s): "424200026"
Test #4:
score: 0
Accepted
time: 1492ms
memory: 111524kb
input:
48 6713156
output:
198541581
result:
ok 1 number(s): "198541581"
Test #5:
score: 0
Accepted
time: 1ms
memory: 5616kb
input:
1 111
output:
6216
result:
ok 1 number(s): "6216"
Test #6:
score: -100
Time Limit Exceeded
input:
28 7304152