QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #631637 | #9451. Expected Waiting Time | ucup-team896# | TL | 0ms | 7772kb | C++14 | 968b | 2024-10-12 09:23:36 | 2024-10-12 09:23:36 |
Judging History
answer
#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
const int N=2e6+5;
int n,Mod,A,B;
int a[N],b[N],H[N],F[N];
inline int qpow(int x,int y,int z=1){
for(;y;(y>>=1)&&(x=(LL)x*x%Mod))if(y&1)z=(LL)z*x%Mod;return z;
}
inline void MAIN(){
cin>>n>>Mod>>b[0]>>A>>B;
for(int i=1;i<=n+n;++i)
b[i]=(1ll*b[i-1]*A+B)%Mod,a[i]=(a[i-1]+b[i]+1)%Mod;
H[0]=1;
for(int i=1;i<=n;++i)
H[i]=qpow(i+1,Mod-2,(4*i-2ll)*H[i-1]%Mod);
for(int i=1;i<=n;++i)
F[i]=(F[i-1]+1ll*H[n-i]*H[i-1])%Mod;
int ans=0;
for(int i=1;i<=n+n;++i)
ans=(ans+(H[n]-F[(n+n-i+1)/2]*2ll)*a[i])%Mod;
ans=qpow(H[n],Mod-2,ans);
cout<<(ans<0?ans+Mod:ans)<<'\n';
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
int t=1;cin>>t;while(t--)MAIN();
return 0;
}
/*
5
1 1000000007 0 1 0
2 1000000007 0 1 1
2 7 5 2 3
3 31 15 6 24
20 1000000007 0 1 0
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7772kb
input:
5 1 1000000007 0 1 0 2 1000000007 0 1 1 2 7 5 2 3 3 31 15 6 24 20 1000000007 0 1 0
output:
1 12 1 21 879705565
result:
ok 5 number(s): "1 12 1 21 879705565"
Test #2:
score: -100
Time Limit Exceeded
input:
4400 3954 1000000007 0 1 0 1306 1000000007 0 1 0 3774 1000000007 0 1 0 3345 1000000007 0 1 0 891 1000000007 0 1 0 2462 1000000007 0 1 0 237 1000000007 0 1 0 26 1000000007 0 1 0 2510 1000000007 0 1 0 637 1000000007 0 1 0 3250 1000000007 0 1 0 3447 1000000007 0 1 0 1222 1000000007 0 1 0 133 1000000007...
output:
440618338 378292891 979368645 915766295 343598158 80867595 161627927 517387931 396936703 42785642 945720545 764273281 186237656 635777911 164064906 548455037 991964184 468137124 561243246 118562285 856945294 642467240 23673926 808943705 897417615 462422554 656411244 204288121 997894281 244685651 762...