QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#709919 | #8339. Rooted Tree | EMTz | AC ✓ | 270ms | 238292kb | C++20 | 1.4kb | 2024-11-04 17:24:40 | 2024-11-04 17:24:41 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
using namespace std;
typedef pair<int,int>PII;
typedef pair<int,PII>PPI;
typedef array<int,3>ar;
const int N=1e7+7;
const int N1=1e9+9;
const int M=1e9+9;
const ull mask = std::chrono::steady_clock::now().time_since_epoch().count();
mt19937_64 rng(time(0));
const int M1=19260817;
const int base=233;
const int base1=131;
const int INF = 0x3f3f3f3f;
int a[N];
int p[N];
int inv[N];
int qpow(int a,int b)
{
int ans=1;
while(b!=0)
{
if(b%2==1) ans=ans*a%M;
a=a*a%M;
b=b>>1;
}
return ans;
}
void solve()
{
int m,k;
cin>>m>>k;
a[0]=1;
p[0]=1;
for(int i=1;i<=k;i++)
{
a[i]=a[i-1]+m-1;
// a[i]%=M;
p[i]=p[i-1]*a[i]%M;
// cout<<p[i]<<"\n";
}
int iv=qpow(p[k],M-2);
// cout<<iv<<"\n";
for(int i=k;i>=1;i--)
{
inv[i]=iv*p[i-1]%M;
iv=iv*a[i]%M;
}
// for (int i=1;i<=k;++i) printf("%lld%c",a[i]," \n"[i==k]);
// for (int i=1;i<=k;++i) printf("%lld%c",inv[i]," \n"[i==k]);
int ans=0;
int E=0;
int leaf=1;
for(int i=1;i<=k;i++)
{
int tmp=(E+1)*m%M;
ans=ans+tmp;
ans%=M;
E=(1ll*E*(leaf-1)%M+tmp)%M*inv[i]%M;
leaf+=m-1;
leaf%=M;
E=(E%M+M)%M;
}
cout<<ans<<"\n";
}
signed main()
{
std::ios::sync_with_stdio(false);
cout.tie(0);cin.tie(0);
int _=1;
// cin>>_;
while(_--)
{
solve();
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 7764kb
input:
6 2
output:
18
result:
ok 1 number(s): "18"
Test #2:
score: 0
Accepted
time: 1ms
memory: 7756kb
input:
2 6
output:
600000038
result:
ok 1 number(s): "600000038"
Test #3:
score: 0
Accepted
time: 11ms
memory: 24728kb
input:
83 613210
output:
424200026
result:
ok 1 number(s): "424200026"
Test #4:
score: 0
Accepted
time: 164ms
memory: 168324kb
input:
48 6713156
output:
198541581
result:
ok 1 number(s): "198541581"
Test #5:
score: 0
Accepted
time: 0ms
memory: 7960kb
input:
1 111
output:
6216
result:
ok 1 number(s): "6216"
Test #6:
score: 0
Accepted
time: 173ms
memory: 180504kb
input:
28 7304152
output:
457266679
result:
ok 1 number(s): "457266679"
Test #7:
score: 0
Accepted
time: 90ms
memory: 104360kb
input:
38 4101162
output:
232117382
result:
ok 1 number(s): "232117382"
Test #8:
score: 0
Accepted
time: 226ms
memory: 237484kb
input:
51 9921154
output:
340670552
result:
ok 1 number(s): "340670552"
Test #9:
score: 0
Accepted
time: 49ms
memory: 51484kb
input:
79 1801157
output:
620550406
result:
ok 1 number(s): "620550406"
Test #10:
score: 0
Accepted
time: 127ms
memory: 134524kb
input:
22 5417157
output:
457449071
result:
ok 1 number(s): "457449071"
Test #11:
score: 0
Accepted
time: 70ms
memory: 83116kb
input:
25 3210162
output:
36368303
result:
ok 1 number(s): "36368303"
Test #12:
score: 0
Accepted
time: 72ms
memory: 77532kb
input:
67 2919160
output:
935195555
result:
ok 1 number(s): "935195555"
Test #13:
score: 0
Accepted
time: 199ms
memory: 210368kb
input:
77 8613163
output:
482832472
result:
ok 1 number(s): "482832472"
Test #14:
score: 0
Accepted
time: 222ms
memory: 238096kb
input:
90 10000000
output:
275581651
result:
ok 1 number(s): "275581651"
Test #15:
score: 0
Accepted
time: 270ms
memory: 238028kb
input:
99 9999999
output:
126087169
result:
ok 1 number(s): "126087169"
Test #16:
score: 0
Accepted
time: 238ms
memory: 238292kb
input:
100 10000000
output:
451590067
result:
ok 1 number(s): "451590067"
Extra Test:
score: 0
Extra Test Passed