QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#584234 | #9376. Game | guyuefangyuan | WA | 48ms | 3824kb | C++14 | 1.7kb | 2024-09-23 10:40:05 | 2024-09-23 10:40:05 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
const int mod = 998244353;
typedef long long ll;
ll n,x,y,a0,a1,b,cnt,cha1,cha2;
ll ans;
inline void read(ll& a)
{
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
s=s*10+ch-'0';
ch=getchar();
}
a=s*w;
}
ll ksm(ll i,ll k)
{
//cout<<"2"<<endl;
ll res=1;
while(k>0)
{
if(k&1)res=res*i%mod;
i=i*i%mod;
k>>=1;
}
return res;
}
ll dp(ll x,ll y)
{
//cout<<"1"<<endl;
ll v=0;
if(x==0)return 0;
if(y==0)return 1;
if(x>y)
{
v+=(cha2*dp(x-y,y))%mod;
v%=mod;
v+=(cha1)%mod;
v%=mod;
}
if(x<=y)
{
v=(cha1*dp(x,y-x))%mod;
}
return v%mod;
}
ll prime(ll x, ll y)
{
ll v=0;
if(a0==0||a1==0){
if(a0==0) return 0;
if(a1==0) return 1;
}
else{
if(x/y>1)
{
//for(int i=1;i<=x/y;i++){v+=cha1*ksm(cha2,i-1)%mod;v%=mod;}
v+=cha1*(1-ksm(cha2,x/y-1))*ksm(1-cha2,mod-2);
v+=dp(x-(x/y)*y,y);
//v+=(ksm(cha2,x/y)*dp(x-x/y*y,y))%mod;
v%=mod;
}
if(y/x>=1)
{
v+=(ksm(cha1,y/x)*dp(x,y-y/x*x))%mod;
v%=mod;
}
return v;
}
}
int main()
{
read(n);
while(n--)
{
ans=0;
read(x);read(y);
read(a0);read(a1);read(b);
cnt=a0+a1;
cha1=a0*ksm(cnt,mod-2)%mod;
cha2=a1*ksm(cnt,mod-2)%mod;
printf("%lld\n",prime(x,y));
}
}
/*
3
1 1
2 2 6
1 3
2 3 6
3 4
7 3 15
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3792kb
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: 48ms
memory: 3824kb
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 191527674 870227707 169499045 -966855587 415694940 974031360 951368934 426243016 864656779 750317399 -295987051 486881524 824329239 198191519 189360084 966510181 512645443 695650039 -907488913 550002158 -177468885 246877045 39876086 667870434 4051966...
result:
wrong answer 6th lines differ - expected: '45779380', found: '191527674'