QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#669297	#8339. Rooted Tree	tuxiaoxiao	TL	1434ms	113256kb	C++14	579b	2024-10-23 18:00:50	2024-10-23 18:00:56

Judging History

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

[2024-10-23 18:00:56]
评测

测评结果：TL
用时：1434ms
内存：113256kb

查看

[2024-10-23 18:00:50]
提交

answer

#include<bits/stdc++.h>
#define f(i,x,y) for(int i=x;i<=y;i++)
#define df(i,x,y) for(int i=x;i>=y;i--)
#define int long long
#define pb push_back
using namespace std;
const int N=1.1e7,P=1e9+9;
int n,f[N],x,y,m,k,g[N],t=1;
int qp(int u,int v)
{
	int e=1;
	while(v)
	{
		if(v & 1)e = e * u % P;
		u = u * u % P;v /= 2;
	}
	return e;
}
signed main()
{
	scanf("%lld%lld",&m,&k);
	f[0]=0;g[0] = 0;
	f(i,0,k-1)f[i + 1] = (f[i] + (g[i] * qp(t,P - 2) % P + 1) * m) % P,g[i + 1] = (g[i] * qp(t,P-2)%P * (t + m -1) + m ) % P,t += m - 1; 
	cout<<f[k];
	return 0;
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 5780kb

input:

6 2

output:

result:

ok 1 number(s): "18"

Test #2:

score: 0

Accepted

time: 1ms

memory: 5788kb

input:

2 6

output:

600000038

result:

ok 1 number(s): "600000038"

Test #3:

score: 0

Accepted

time: 134ms

memory: 15912kb

input:

83 613210

output:

424200026

result:

ok 1 number(s): "424200026"

Test #4:

score: 0

Accepted

time: 1434ms

memory: 113256kb

input:

48 6713156

output:

198541581

result:

ok 1 number(s): "198541581"

Test #5:

score: 0

Accepted

time: 1ms

memory: 5812kb

input:

1 111

output:

result:

ok 1 number(s): "6216"

Test #6:

score: -100

Time Limit Exceeded

input:

28 7304152

output:

457266679