QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#462383#8339. Rooted TreeztttttTL 202ms97880kbC++141.1kb2024-07-03 18:37:412024-07-03 18:37:42

Judging History

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

  • [2024-07-03 18:37:42]
  • 评测
  • 测评结果:TL
  • 用时:202ms
  • 内存:97880kb
  • [2024-07-03 18:37:41]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e7+10,M=1e9+9;
int f[N],ny[N],dp[N],zt[N];
int ksm(int a,int b,int c){
	int b1=b;
	zt[1]=a%c;
	int cnt=1;
	int ans=1;
	while(b1){
		cnt++;
		zt[cnt]=zt[cnt-1]*zt[cnt-1]%c;
		b1>>=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; 
	int maxx=1;
	for(int i=1;i<=k;i++){
		f[i]=f[i-1]-1+m;
		maxx=max(maxx,f[i]);
	}
	//for(int i=1;i<=k;i++)cout<<f[i]<<endl;
    if(maxx>10000000)maxx=10000000;
	dp[0]=0;
	ny[1]=1;
	for(int i=2;i<=maxx;i++){
		ny[i]=(M-M/i)*ny[M%i]%M;
	}
	for(int i=1;i<=k;i++){
		if(f[i]<=1e7){
			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=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;
} 

详细

Test #1:

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

input:

6 2

output:

18

result:

ok 1 number(s): "18"

Test #2:

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

input:

2 6

output:

600000038

result:

ok 1 number(s): "600000038"

Test #3:

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

input:

83 613210

output:

424200026

result:

ok 1 number(s): "424200026"

Test #4:

score: -100
Time Limit Exceeded

input:

48 6713156

output:

198541581

result: