QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #669294 | #8339. Rooted Tree | tuxiaoxiao | RE | 126ms | 18380kb | C++14 | 579b | 2024-10-23 18:00:05 | 2024-10-23 18:00:06 |
Judging History
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.1e6,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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5828kb
input:
6 2
output:
18
result:
ok 1 number(s): "18"
Test #2:
score: 0
Accepted
time: 0ms
memory: 5828kb
input:
2 6
output:
600000038
result:
ok 1 number(s): "600000038"
Test #3:
score: 0
Accepted
time: 126ms
memory: 18380kb
input:
83 613210
output:
424200026
result:
ok 1 number(s): "424200026"
Test #4:
score: -100
Runtime Error
input:
48 6713156