QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#583206#9376. GameChief_NingWA 56ms3616kbC++142.9kb2024-09-22 18:57:482024-09-22 18:57:52

Judging History

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

  • [2024-09-22 18:57:52]
  • 评测
  • 测评结果:WA
  • 用时:56ms
  • 内存:3616kb
  • [2024-09-22 18:57:48]
  • 提交

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'