QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #716934 | #8339. Rooted Tree | icpc_zhzx034# | AC ✓ | 1050ms | 3944kb | C++14 | 1.2kb | 2024-11-06 16:25:01 | 2024-11-06 16:25:02 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> Pr;
#define fi first
#define se second
#define mkp make_pair
#define pb emplace_back
// #define mid ((l+r)>>1)
#define popcnt __builtin_popcountll
const ll mod = 1e9+9;
inline ll read(){
ll x=0, f=1; char ch=getchar();
while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
return x*f;
}
inline ll lg2(ll x){ return 63^__builtin_clzll(x); }
inline ll qpow(ll a,ll b){
ll ans=1, base=a;
while(b){
if(b&1) ans=ans*base%mod;
base=base*base%mod; b>>=1;
}
return ans;
}
void init(){ }
inline ll inv(ll x){ return qpow(x, mod-2); }
ll M, K;
void procedure(){
M=read(), K=read();
ll f = 0, ans = K * M % mod;
ll tot = 0;
int nd = 1;
for(int i=1;i<=K;i++){
tot = (tot + f) % mod;
f = (f + inv((M-1)*i+1)) % mod;
}
printf("%lld\n", (ans + tot * M * M) % mod );
}
int main(){
#ifdef LOCAL
assert(freopen("input.txt","r",stdin));
assert(freopen("output.txt","w",stdout));
#endif
ll T=1;
init();
while(T--) procedure();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3724kb
input:
6 2
output:
18
result:
ok 1 number(s): "18"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
2 6
output:
600000038
result:
ok 1 number(s): "600000038"
Test #3:
score: 0
Accepted
time: 65ms
memory: 3788kb
input:
83 613210
output:
424200026
result:
ok 1 number(s): "424200026"
Test #4:
score: 0
Accepted
time: 705ms
memory: 3812kb
input:
48 6713156
output:
198541581
result:
ok 1 number(s): "198541581"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
1 111
output:
6216
result:
ok 1 number(s): "6216"
Test #6:
score: 0
Accepted
time: 767ms
memory: 3940kb
input:
28 7304152
output:
457266679
result:
ok 1 number(s): "457266679"
Test #7:
score: 0
Accepted
time: 431ms
memory: 3784kb
input:
38 4101162
output:
232117382
result:
ok 1 number(s): "232117382"
Test #8:
score: 0
Accepted
time: 1041ms
memory: 3796kb
input:
51 9921154
output:
340670552
result:
ok 1 number(s): "340670552"
Test #9:
score: 0
Accepted
time: 190ms
memory: 3880kb
input:
79 1801157
output:
620550406
result:
ok 1 number(s): "620550406"
Test #10:
score: 0
Accepted
time: 569ms
memory: 3944kb
input:
22 5417157
output:
457449071
result:
ok 1 number(s): "457449071"
Test #11:
score: 0
Accepted
time: 337ms
memory: 3796kb
input:
25 3210162
output:
36368303
result:
ok 1 number(s): "36368303"
Test #12:
score: 0
Accepted
time: 303ms
memory: 3796kb
input:
67 2919160
output:
935195555
result:
ok 1 number(s): "935195555"
Test #13:
score: 0
Accepted
time: 904ms
memory: 3804kb
input:
77 8613163
output:
482832472
result:
ok 1 number(s): "482832472"
Test #14:
score: 0
Accepted
time: 1050ms
memory: 3680kb
input:
90 10000000
output:
275581651
result:
ok 1 number(s): "275581651"
Test #15:
score: 0
Accepted
time: 1050ms
memory: 3808kb
input:
99 9999999
output:
126087169
result:
ok 1 number(s): "126087169"
Test #16:
score: 0
Accepted
time: 1050ms
memory: 3804kb
input:
100 10000000
output:
451590067
result:
ok 1 number(s): "451590067"
Extra Test:
score: 0
Extra Test Passed