QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#584234#9376. GameguyuefangyuanWA 48ms3824kbC++141.7kb2024-09-23 10:40:052024-09-23 10:40:05

Judging History

你现在查看的是最新测评结果

  • [2024-09-23 10:40:05]
  • 评测
  • 测评结果:WA
  • 用时:48ms
  • 内存:3824kb
  • [2024-09-23 10:40:05]
  • 提交

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'