QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#569061#8339. Rooted TreeayxrakzilTL 142ms9640kbC++141.1kb2024-09-16 20:16:102024-09-16 20:16:11

Judging History

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

  • [2024-09-16 20:16:11]
  • 评测
  • 测评结果:TL
  • 用时:142ms
  • 内存:9640kb
  • [2024-09-16 20:16:10]
  • 提交

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

result: