QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#685398#8339. Rooted Treeucup-team1412TL 1492ms111524kbC++23879b2024-10-28 19:15:442024-10-28 19:15:44

Judging History

你现在查看的是最新测评结果

  • [2024-10-28 19:15:44]
  • 评测
  • 测评结果:TL
  • 用时:1492ms
  • 内存:111524kb
  • [2024-10-28 19:15:44]
  • 提交

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

output:


result: