QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#730047#8339. Rooted Treeehuohz#WA 54ms3948kbC++14808b2024-11-09 18:27:432024-11-09 18:27:43

Judging History

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

  • [2024-11-09 18:27:43]
  • 评测
  • 测评结果:WA
  • 用时:54ms
  • 内存:3948kb
  • [2024-11-09 18:27:43]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+9;
int M,K;
inline int qm(int x) {return x>=mod?x-mod:x;}
inline int ksm(int a,int b) {
    int S=1;for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) S=1ll*S*a%mod;return S;
}
int main() {
    scanf("%d%d",&M,&K);
    int pre = 0;
    int sz = 1;
    for(int i=1;i<=K;++i) {
        int num = 1 + (i-1)*(M-1);
        int now =  qm(qm(1ll*pre*(M-1)%mod + 1ll*sz*M%mod*num%mod) + 1ll*pre*num%mod);
        sz = 1ll*sz*num%mod;
        pre = now;
        //cout<<now<<" "<<sz<<" " <<pre<<endl;
    }
    int dep_s = 1ll*pre*ksm(sz,mod-2)%mod;
    //cout<<sz<<" "<<dep_s<<endl;
    dep_s = (dep_s - 1ll*K*M%mod + mod)%mod;
    dep_s = 1ll*dep_s*ksm(M-1,mod-2)%mod;
    printf("%d\n",qm(1ll*dep_s*M%mod + 1ll*K*M%mod));
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3880kb

input:

6 2

output:

18

result:

ok 1 number(s): "18"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3764kb

input:

2 6

output:

600000038

result:

ok 1 number(s): "600000038"

Test #3:

score: 0
Accepted
time: 5ms
memory: 3940kb

input:

83 613210

output:

424200026

result:

ok 1 number(s): "424200026"

Test #4:

score: 0
Accepted
time: 54ms
memory: 3948kb

input:

48 6713156

output:

198541581

result:

ok 1 number(s): "198541581"

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3940kb

input:

1 111

output:

111

result:

wrong answer 1st numbers differ - expected: '6216', found: '111'