QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#583220#9376. GameChief_NingWA 261ms3712kbC++143.0kb2024-09-22 19:03:092024-09-22 19:03:09

Judging History

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

  • [2024-09-22 19:03:09]
  • 评测
  • 测评结果:WA
  • 用时:261ms
  • 内存:3712kb
  • [2024-09-22 19:03:09]
  • 提交

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)%mod,pb=(b*inv(a+b)+mod)%mod;
    if(x==y){
        cout<<(pa+mod)%mod<<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);
                ans%=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);
            ans%=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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3656kb

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: 51ms
memory: 3712kb

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: 261ms
memory: 3592kb

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:

956244106
630390274
291994607
615886125
237109764
508160251
331153702
393310721
954343790
797056532
381872596
626475273
62673737
630078498
476888583
562070336
641337362
619652293
129272327
193823633
919752488
992265631
924687199
426928147
684986504
141679225
702615422
36765716
364902017
651180620
20...

result:

wrong answer 1st lines differ - expected: '623291477', found: '956244106'