QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#388402#8339. Rooted Treeucup-team3282#AC ✓206ms159836kbC++14828b2024-04-13 15:15:222024-04-13 15:15:23

Judging History

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

  • [2024-04-13 15:15:23]
  • 评测
  • 测评结果:AC
  • 用时:206ms
  • 内存:159836kb
  • [2024-04-13 15:15:22]
  • 提交

answer

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int mod=1e9+9;
const int maxk=1e7+10;

int qpow(int a,int b=mod-2){
	int res=1;
	while(b){
		if(b&1)
			res=(ll)res*a%mod;
		a=(ll)a*a%mod;
		b>>=1;
	}
	return res;
}

int s[maxk],sv[maxk],inv[maxk],a[maxk];

int E=0;
int main(){
    int m,k,Kl=1,El=0;
    cin>>m>>k;
    
    a[0]=1;
    for(int i=1;i<=k;i++)
    	a[i]=a[i-1]+m-1;
    s[0]=1;
	for(int i=1;i<=k;i++)
		s[i]=(ll)s[i-1]*a[i]%mod;
	sv[k]=qpow(s[k]);
	for(int i=k;i;i--)
		sv[i-1]=(ll)sv[i]*a[i]%mod;
	for(int i=1;i<=k;i++)
		inv[i]=(ll)sv[i]*s[i-1]%mod;
    
    int i=1;
    while(k--){
        E=(E+(ll)(El+1)*m)%mod;
        El=((ll)El*(a[i-1]-1)+(ll)m*(El+1))%mod*inv[i]%mod;
        i++;
    }
    cout<<E<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 9796kb

input:

6 2

output:

18

result:

ok 1 number(s): "18"

Test #2:

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

input:

2 6

output:

600000038

result:

ok 1 number(s): "600000038"

Test #3:

score: 0
Accepted
time: 11ms
memory: 19732kb

input:

83 613210

output:

424200026

result:

ok 1 number(s): "424200026"

Test #4:

score: 0
Accepted
time: 121ms
memory: 112096kb

input:

48 6713156

output:

198541581

result:

ok 1 number(s): "198541581"

Test #5:

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

input:

1 111

output:

6216

result:

ok 1 number(s): "6216"

Test #6:

score: 0
Accepted
time: 146ms
memory: 126052kb

input:

28 7304152

output:

457266679

result:

ok 1 number(s): "457266679"

Test #7:

score: 0
Accepted
time: 90ms
memory: 76376kb

input:

38 4101162

output:

232117382

result:

ok 1 number(s): "232117382"

Test #8:

score: 0
Accepted
time: 203ms
memory: 159596kb

input:

51 9921154

output:

340670552

result:

ok 1 number(s): "340670552"

Test #9:

score: 0
Accepted
time: 38ms
memory: 35792kb

input:

79 1801157

output:

620550406

result:

ok 1 number(s): "620550406"

Test #10:

score: 0
Accepted
time: 97ms
memory: 92896kb

input:

22 5417157

output:

457449071

result:

ok 1 number(s): "457449071"

Test #11:

score: 0
Accepted
time: 66ms
memory: 60208kb

input:

25 3210162

output:

36368303

result:

ok 1 number(s): "36368303"

Test #12:

score: 0
Accepted
time: 60ms
memory: 59936kb

input:

67 2919160

output:

935195555

result:

ok 1 number(s): "935195555"

Test #13:

score: 0
Accepted
time: 179ms
memory: 142624kb

input:

77 8613163

output:

482832472

result:

ok 1 number(s): "482832472"

Test #14:

score: 0
Accepted
time: 206ms
memory: 159832kb

input:

90 10000000

output:

275581651

result:

ok 1 number(s): "275581651"

Test #15:

score: 0
Accepted
time: 202ms
memory: 159772kb

input:

99 9999999

output:

126087169

result:

ok 1 number(s): "126087169"

Test #16:

score: 0
Accepted
time: 201ms
memory: 159836kb

input:

100 10000000

output:

451590067

result:

ok 1 number(s): "451590067"

Extra Test:

score: 0
Extra Test Passed