QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#730047 | #8339. Rooted Tree | ehuohz# | WA | 54ms | 3948kb | C++14 | 808b | 2024-11-09 18:27:43 | 2024-11-09 18:27:43 |
Judging History
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'