QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#583206 | #9376. Game | Chief_Ning | WA | 56ms | 3616kb | C++14 | 2.9kb | 2024-09-22 18:57:48 | 2024-09-22 18:57:52 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define endl "\n"
#define pq priority_queue<int>
#define rep(i,a,n) for(int i=a;i<n;i++)
#define debug1(x) cout<<x<<endl;
#define debug2(a,b) cout<<a<<" "<<b<<endl;
const int INF = 0x3f3f3f3f;//无穷大
const int inf = 0xc0c0c0c0;//无穷小
const int mod = 998244353;
const int N = 1;
/*
________ ___ ___ ___ _______ ________ ________ ___ ________ ________
|\ ____\|\ \|\ \|\ \|\ ___ \ |\ _____\\ ___ \|\ \|\ ___ \|\ ____\
\ \ \___|\ \ \\\ \ \ \ \ __/|\ \ \__/\ \ \\ \ \ \ \ \ \\ \ \ \ \___|
\ \ \ \ \ __ \ \ \ \ \_|/_\ \ __\\ \ \\ \ \ \ \ \ \\ \ \ \ \ ___
\ \ \____\ \ \ \ \ \ \ \ \_|\ \ \ \_| \ \ \\ \ \ \ \ \ \\ \ \ \ \|\ \
\ \_______\ \__\ \__\ \__\ \_______\ \__\ \ \__\\ \__\ \__\ \__\\ \__\ \_______\
\|_______|\|__|\|__|\|__|\|_______|\|__| \|__| \|__|\|__|\|__| \|__|\|_______|
*/
ll fpm(ll a,ll b) {
a%=mod;
ll ans = 1;
while (b) {
if (b & 1)
ans = (ans * a) % mod;
b >>= 1;
a = (a * a) % mod;
}
return ans;
}
ll inv(int x){
return fpm(x,mod-2);
}
void ChiefNing()
{
int x,y;
cin>>x>>y;
int a,b,c;
cin>>a>>b>>c;
int pa=a*inv(a+b)%mod,pb=b*inv(a+b)%mod;
if(x==y){
cout<<pa<<endl;
return ;
}
int ans=0,now=1;
bool is=0;//表示是否第一次达到
while(x!=y){
if(x<y){
if(is){
int cs=y/x;
y-=(cs*x);
if(y==0){
cs--;
y=x;
}
int fz=now*pa%mod*pa%mod*(1- fpm(pa,cs)+mod)%mod,fm=1-pa;
ans+=(fz*inv(fm)%mod);
now*=fpm(pa,cs);
now%=mod;
}
else{
int cs=y/x;
y-=(cs*x);
if(y==0){
cs--;
y=x;
}
now*= (fpm(pa,cs)%mod);
now%=mod;
}
}
else{
if(!is){
ans+=((now*pa)%mod);
ans%=mod;
}//此时是第一次满足,那么需要乘一下当前值
is=1;
int cs=x/y;
x-=(cs*y);
if(x==0){
cs--;
x=y;
}
int fz=now*pa%mod*pb%mod*(1- fpm(pb,cs)+mod)%mod,fm=1-pb;
ans+=(fz*inv(fm)%mod);
now*=fpm(pb,cs);
now%=mod;
}
}
if(!is)ans+=((now*pa)%mod);
cout<<ans%mod<<endl;
}
signed main(void)
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int _;
cin>>_;
while(_--)
ChiefNing();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3608kb
input:
3 1 1 2 2 6 1 3 2 3 6 3 4 7 3 15
output:
499122177 910398850 220911476
result:
ok 3 lines
Test #2:
score: -100
Wrong Answer
time: 56ms
memory: 3616kb
input:
100000 1 1000000000 12980050 128257807 266126484 1 1000000000 400255084 123438563 768881284 1000000000 1000000000 24563487 72082135 450057094 1 1000000000 56952077 40876000 193815114 1000000000 1000000000 82048274 239365585 326520865 1000000000 1 309821265 346013425 963168258 1 1 104158269 199365020...
output:
947058399 376449942 612621163 138416357 592200562 45779380 870227707 169499045 86396463 415694940 46851356 951368934 426243016 864656779 750317399 -75787993 486881524 824329239 198191519 189360084 966510181 512645443 695650039 -295143570 550002158 -559774171 246877045 39876086 667870434 405196653 59...
result:
wrong answer 16th lines differ - expected: '922456360', found: '-75787993'