QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#462643#8339. Rooted TreeztttttAC ✓1471ms159912kbC++141.9kb2024-07-03 22:51:582024-07-03 22:51:58

Judging History

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

  • [2024-07-03 22:51:58]
  • 评测
  • 测评结果:AC
  • 用时:1471ms
  • 内存:159912kb
  • [2024-07-03 22:51:58]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e7+10,M=1e9+9;
int ny[N],dp[N],zt[N],maxx,f[N];
int ksm(int a,int b,int c){
//	int b1=b;
	zt[1]=a%c;
	int cnt=1;
	int ans=1;
	while(b){
		if(b&1){
			//cnt++;
			ans*=zt[cnt];
			ans%=c; 
		}
		cnt++;
		zt[cnt]=zt[cnt-1]*zt[cnt-1]%c;
		
		b>>=1;
	}
//	cnt=0;
//	while(b){
//		cnt++;
//		if(b&1){
//			//cnt++;
//			ans*=zt[cnt];
//			ans%=c; 
//		}
//		b>>=1;
//	}
	return ans;
}
signed main(){
	int m,k;
	cin>>m>>k;
	f[0]=1; 
	for(int i=1;i<=k;i++){
		f[i]=f[i-1]-1+m;
		
	}
	//for(int i=1;i<=k;i++)cout<<f[i]<<endl;
//    if(f[k]>10000000)maxx=10000000;
//    else maxx=f[k];
	dp[0]=0;
//	ny[1]=1;
//	for(int i=m;i<=f[k];i+=m-1){
//		cout<<i<<" "<<M%i<<" "<<ny[M%i]<<endl;
//		ny[i]=(M-M/i)*ny[M%i]%M;
//	}
//int ans1=0; 
	for(int i=1;i<=k;i++){
//		if(f[i]<=1e7){
//cout<<M%f[i]<<endl;
//if(f[i]<=50000000){
//	if(M%f[i]<=50000000&&ny[M%f[i]]){
//			ny[f[i]]=(M-M/f[i])*ny[M%f[i]]%M;
//			}else{
//				ny[f[i]]=ksm(f[i],M-2,M);
//			} 
//			dp[i]=((dp[i-1]*f[i-1])%M*ny[f[i]]%M-(dp[i-1]*ny[f[i]]%M)+M)%M+m*dp[i-1]%M*ny[f[i]]%M+m*ny[f[i]]%M;
//			dp[i]%=M;
//}else{
//	int zqx;
//	if(M%f[i]<=50000000&&ny[M%f[i]]){
//			zqx=(M-M/f[i])*ny[M%f[i]]%M;
//			}else{
//				zqx=ksm(f[i],M-2,M);
//			}
int zqx=ksm(f[i],M-2,M);
			//dp[i]=((dp[i-1]*f[i-1])%M*zqx%M-(dp[i-1]*zqx%M)+M)%M+m*dp[i-1]%M*zqx%M+m*zqx%M;
			dp[i]=(dp[i-1]*(f[i-1]-1+m)%M+m)*zqx;
			dp[i]%=M;
//}
//            ans1+=dp[i]%M;
//            ans1%=M;
			//cout<<i<<" "<<dp[i]<<endl;
//		}else{
//			int zqx=ksm(f[i],M-2,M);
//			dp[i]=((dp[i-1]*f[i-1])%M*zqx%M-(dp[i-1]*zqx%M)+M)%M+m*dp[i-1]%M*zqx%M+m*zqx%M;
//			dp[i]%=M;
//		}
	}
	//for(int i=1;i<=k;i++)cout<<dp[i]<<endl;
	int ans1=dp[k]*f[k]%M;
	for(int i=1;i<k;i++){
		ans1=ans1+dp[i]%M;
		ans1%=M;
	}
	cout<<ans1<<endl;
	return 0;
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

6 2

output:

18

result:

ok 1 number(s): "18"

Test #2:

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

input:

2 6

output:

600000038

result:

ok 1 number(s): "600000038"

Test #3:

score: 0
Accepted
time: 78ms
memory: 13140kb

input:

83 613210

output:

424200026

result:

ok 1 number(s): "424200026"

Test #4:

score: 0
Accepted
time: 974ms
memory: 108412kb

input:

48 6713156

output:

198541581

result:

ok 1 number(s): "198541581"

Test #5:

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

input:

1 111

output:

6216

result:

ok 1 number(s): "6216"

Test #6:

score: 0
Accepted
time: 1070ms
memory: 117704kb

input:

28 7304152

output:

457266679

result:

ok 1 number(s): "457266679"

Test #7:

score: 0
Accepted
time: 605ms
memory: 67744kb

input:

38 4101162

output:

232117382

result:

ok 1 number(s): "232117382"

Test #8:

score: 0
Accepted
time: 1449ms
memory: 158664kb

input:

51 9921154

output:

340670552

result:

ok 1 number(s): "340670552"

Test #9:

score: 0
Accepted
time: 272ms
memory: 31800kb

input:

79 1801157

output:

620550406

result:

ok 1 number(s): "620550406"

Test #10:

score: 0
Accepted
time: 799ms
memory: 88188kb

input:

22 5417157

output:

457449071

result:

ok 1 number(s): "457449071"

Test #11:

score: 0
Accepted
time: 470ms
memory: 53688kb

input:

25 3210162

output:

36368303

result:

ok 1 number(s): "36368303"

Test #12:

score: 0
Accepted
time: 429ms
memory: 49216kb

input:

67 2919160

output:

935195555

result:

ok 1 number(s): "935195555"

Test #13:

score: 0
Accepted
time: 1256ms
memory: 138084kb

input:

77 8613163

output:

482832472

result:

ok 1 number(s): "482832472"

Test #14:

score: 0
Accepted
time: 1457ms
memory: 159728kb

input:

90 10000000

output:

275581651

result:

ok 1 number(s): "275581651"

Test #15:

score: 0
Accepted
time: 1464ms
memory: 159892kb

input:

99 9999999

output:

126087169

result:

ok 1 number(s): "126087169"

Test #16:

score: 0
Accepted
time: 1471ms
memory: 159912kb

input:

100 10000000

output:

451590067

result:

ok 1 number(s): "451590067"

Extra Test:

score: 0
Extra Test Passed