QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#582624 | #9376. Game | Swd146296# | WA | 195ms | 3632kb | C++14 | 863b | 2024-09-22 17:01:20 | 2024-09-22 17:01:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=998244353ll;
int _;
int x,y,a,b,d,sub,sinv;
ll ksm(ll a,ll b){
ll res=1;
while(b){
if(b&1)res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
ll norm(ll x){
return ((x%mod)+mod)%mod;
}
ll solve(int x,int y){
if(x==y)return a*sinv%mod;//turansiwang
if(x<y){//bunengshu
int times=y/x;
if(y==x*times)times-=1;
int newy=y-x*times;
ll bushu=ksm(a*sinv%mod,times);
return solve(x,newy)*bushu%mod;
}
if(x>y){//zhiyao yingyiba
int times=x/y;
if(x==y*times)times-=1;
int newx=x-y*times;
ll ying=norm(1-ksm(b*sinv%mod,times));
return norm(ying+norm(1-ying)*solve(newx,y)%mod);
}
}
int main(){
cin>>_;
while(_--){
cin>>x>>y;
cin>>a>>b>>sub;
sub=a+b;
sinv=ksm(sub,mod-2);
cout<<solve(x,y)<<endl;
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3596kb
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: 195ms
memory: 3632kb
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:
23409871 109354877 683273820 241464537 -642876456 603651894 866111085 -27984652 252811383 31644570 891062361 942959651 -433710537 -265382174 802636063 278805887 -69267389 346523045 -41028232 170484524 73605878 55001858 -544733033 602843698 851970839 760828265 659400395 182568424 -553127905 930884311...
result:
wrong answer 1st lines differ - expected: '947058399', found: '23409871'