QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#583211 | #9376. Game | Chief_Ning | WA | 260ms | 3708kb | C++14 | 2.9kb | 2024-09-22 18:58:55 | 2024-09-22 18:58:56 |
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)%mod<<endl;
}
signed main(void)
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int _;
cin>>_;
while(_--)
ChiefNing();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3660kb
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: 0
Accepted
time: 57ms
memory: 3708kb
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 922456360 486881524 824329239 198191519 189360084 966510181 512645443 695650039 703100783 550002158 438470182 246877045 39876086 667870434 405196653 5935...
result:
ok 100000 lines
Test #3:
score: -100
Wrong Answer
time: 260ms
memory: 3588kb
input:
100000 167959139 481199252 18199423 25950409 149762920 773386884 579721198 16629525 28339910 152155823 2087506 268792718 43528658 6471925 90197530 691952768 717268783 516613092 94328992 743662288 45277106 856168102 309821265 346013425 963168258 279198849 527268921 30167950 166388455 577970339 140515...
output:
-42000247 -367854079 -706249746 -382358228 -761134589 -490084102 -667090651 -604933632 -43900563 -201187821 -616371757 -371769080 -935570616 -368165855 -521355770 -436174017 -356906991 -378592060 -868972026 -804420720 -78491865 -5978722 -73557154 -571316206 -313257849 -856565128 -295628931 -96147863...
result:
wrong answer 1st lines differ - expected: '623291477', found: '-42000247'