QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#619592 | #8339. Rooted Tree | lzy | TL | 1499ms | 3700kb | C++14 | 616b | 2024-10-07 14:43:52 | 2024-10-07 14:43:52 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
int mod=1e9+9;
int qpow(int a,int b){
int res=1;
while(b){
if(b&1)res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
signed main() {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n,k;
cin>>n>>k;
int av;
int sum=0,leave=0,siz2=1;
for(int i=1;i<=k;i++){
av=leave*qpow(siz2,mod-2)%mod;
int t=((av+1)*n)%mod;
sum=(sum+t)%mod;
leave=(leave+t-av+mod)%mod;
siz2=(siz2+n-1)%mod;
}
cout<<sum<<"\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3576kb
input:
6 2
output:
18
result:
ok 1 number(s): "18"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
2 6
output:
600000038
result:
ok 1 number(s): "600000038"
Test #3:
score: 0
Accepted
time: 138ms
memory: 3700kb
input:
83 613210
output:
424200026
result:
ok 1 number(s): "424200026"
Test #4:
score: 0
Accepted
time: 1499ms
memory: 3580kb
input:
48 6713156
output:
198541581
result:
ok 1 number(s): "198541581"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
1 111
output:
6216
result:
ok 1 number(s): "6216"
Test #6:
score: -100
Time Limit Exceeded
input:
28 7304152