QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#619592#8339. Rooted TreelzyTL 1499ms3700kbC++14616b2024-10-07 14:43:522024-10-07 14:43:52

Judging History

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

  • [2024-10-07 14:43:52]
  • 评测
  • 测评结果:TL
  • 用时:1499ms
  • 内存:3700kb
  • [2024-10-07 14:43:52]
  • 提交

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

output:


result: