QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#668896#8339. Rooted Treebeidiaodajht#TL 143ms3804kbC++232.2kb2024-10-23 16:29:372024-10-23 16:29:38

Judging History

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

  • [2024-10-23 16:29:38]
  • 评测
  • 测评结果:TL
  • 用时:143ms
  • 内存:3804kb
  • [2024-10-23 16:29:37]
  • 提交

answer

// #include<bits/stdc++.h>
// using namespace std;
// int n,b[1005];
// vector<pair<int,int> >ans;
// void solve(int l,int r){
// 	if(l==r) return ;
// 	int mid=(l+r)>>1;
// 	for(int i=1;i<=n;++i) if(b[i]>mid&&b[i]<=r) ans.emplace_back(make_pair(2,i));
// 	for(int i=l+1;i<=mid;++i) ans.emplace_back(make_pair(1,i));
// 	solve(l,mid);solve(mid+1,r);
// }
// int main(){
// 	scanf("%d",&n);
// 	for(int i=1;i<=n;++i) scanf("%d",&b[i]);
// 	solve(0,n);
// 	printf("%d\n",ans.size());
// 	for(auto a:ans) printf("%d %d\n",a.first,a.second);
// 	return 0;
// }
//A

// #include<bits/stdc++.h>
// #define M 100005
// using namespace std;
// int n,_4,_5,fa[M],Fa[M],dep[M],du[M],U,V;
// long long ans;
// vector<int> e[M];
// void dfs(int u,int fa){
// 	for(int v:e[u]) if(v!=fa){
// 		dep[v]=dep[u]+1;Fa[v]=u;
// 		dfs(v,u);
// 	}
// }
// void del(int x){
// 	_4-=(du[x]==4);_5-=(du[x]==5);
// 	du[x]--;
// 	_4+=(du[x]==4);_5+=(du[x]==5);
// }
// void add(int x){
// 	_4-=(du[x]==4);_5-=(du[x]==5);
// 	du[x]++;
// 	_4+=(du[x]==4);_5+=(du[x]==5);
// }
// int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
// int main(){
// 	scanf("%d",&n);
// 	for(int i=1;i<=n;++i) fa[i]=i;
// 	for(int i=1,u,v;i<=n;++i){
// 		scanf("%d%d",&u,&v);du[u]++;du[v]++;
// 		if(find(u)!=find(v)) e[u].emplace_back(v),e[v].emplace_back(u),fa[find(u)]=find(v);
// 		else U=u,V=v;
// 	}
// 	// printf("%d %d\n",U,V);
// 	for(int i=1;i<=n;++i) _4+=(du[i]==4),_5+=(du[i]==5);
// 	dfs(1,0);
// 	del(U);del(V);if(!_5) ans+=n-_4;add(U);add(V);
// 	while(U!=V){
// 		if(dep[V]>dep[U]) swap(U,V);
// 		del(U);del(Fa[U]);
// 		if(!_5) ans+=n-_4;
// 		add(U);add(Fa[U]);U=Fa[U];
// 	}
// 	printf("%lld",ans);
// 	return 0;
// }
//F

#include<bits/stdc++.h>
#define mod 1000000009
using namespace std;
long long m,k;
int mi(int a,int b=mod-2){
	int ans=1;
	while(b){
		if(b&1) ans=1ll*ans*a%mod;
		b>>=1;a=1ll*a*a%mod;
	}
	return ans;
}
int main(){
	scanf("%lld%lld",&m,&k);
	long long nw=0,lf=0;
	for(int i=1;i<=k;++i){
		nw=(1ll*(lf+1)*m%mod+1ll*nw*(1+(i-1)*m)%mod)*mi((1ll*i*m+1)%mod)%mod;
		lf+=1ll*m*mi((1ll+1ll*i*(m-1))%mod)%mod;lf%=mod;
	}
	nw=nw*(1+1ll*k*m)%mod;
	printf("%lld",nw);	
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3696kb

input:

6 2

output:

18

result:

ok 1 number(s): "18"

Test #2:

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

input:

2 6

output:

600000038

result:

ok 1 number(s): "600000038"

Test #3:

score: 0
Accepted
time: 143ms
memory: 3692kb

input:

83 613210

output:

424200026

result:

ok 1 number(s): "424200026"

Test #4:

score: -100
Time Limit Exceeded

input:

48 6713156

output:

198541581

result: