QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#583715#9376. GamejcybtdAC ✓205ms3704kbC++111.8kb2024-09-22 21:27:562024-09-22 21:28:00

Judging History

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

  • [2024-09-22 21:28:00]
  • 评测
  • 测评结果:AC
  • 用时:205ms
  • 内存:3704kb
  • [2024-09-22 21:27:56]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod = 998244353; 

ll pa, pb;

ll ksm(ll a, ll b){
	a %= mod;
	//b %= mod;
	ll res = 1;
	while(b){
		if(b & 1) res = (res * a) % mod;
		a = (a * a) % mod;
		b >>= 1;
	} 
	return res;
}

//ll f(ll x, ll y){//返回awin的概率 
//	if(x <= y){
//		ll kb = y / x;
//		if(y % x == 0) return ksm(pa, kb);
//		return ksm(pa, kb) * f(x, y % x) % mod;
//	}
//	else{
//		ll kb = x / y;
//		if(x % y == 0) return (1 - ksm(pb, kb) + mod) % mod;
//		// y min calc py, 
//		ll py = ksm(pb, kb) * ((1 - f(x % y, y)) % mod + mod) % mod;
//		ll px = ((1 - py) % mod + mod) % mod;
//		return px; 
//		return ((1 - ksm(pb, kb) * ((1 - f(x % y, y) + mod) % mod) % mod + mod) % mod);
//	}
//}

ll f(ll x, ll y){
	if(x <= y){
		ll kb = y / x;
		if(y % x == 0) return ksm(pa, kb);
		return ksm(pa, kb) * f(x, y % x) % mod;
	}
	else{
		ll kb = x / y;
		if(x % y == 0){
			//return ((1ll - ksm(pb, kb - 1)) % mod + mod) % mod * f(y, y) % mod; 
			return ((1ll - ksm(pb, kb)) % mod + mod) % mod;
		}
		ll py = ksm(pb, kb) * (((1ll - f(x % y, y)) % mod + mod) % mod) % mod;
		ll px = ((1ll - py) % mod + mod) % mod;
		return px % mod;
	}
}

void solve(){
	ll x, y;
	ll a, b, c;
	
	cin >> x >> y >> a >> b >> c;
	ll tmp = a + b;
	pa = a * ksm(tmp, mod - 2) % mod;
	pb = b * ksm(tmp, mod - 2) % mod; 
	//cout << "pa = " << pa << " pb = " << pb << endl;
	cout << f(x, y) << endl;
} 

void get(ll a, ll b){
	a %= mod;
	b %= mod;
	cout << a * ksm(b, mod - 2) % mod << endl;
}

int main(){
//	ll rr = 12980050 * ksm(12980050 + 128257807, mod - 2) % mod;
//	cout << rr << endl;
//	cout << ksm(rr, 1e9);
//	cout << "ksm = " << ksm( 732401240, 1e9) << endl;
	//get()
	int t;
	cin >> t;
	while(t--){
		solve();
	}
	return 0;
} 

/*
1000000 1
1 1 1
444030275
*/

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

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

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: 156ms
memory: 3704kb

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: 0
Accepted
time: 197ms
memory: 3624kb

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:

623291477
8294925
601180149
463883218
142231120
497599259
476659890
155417812
443629949
455506204
904783575
385844451
808860628
149767602
10830828
677371444
448503075
706413653
597810956
870426972
360524784
345163088
257088594
375675323
6636182
872339516
51833722
26823600
25949962
82719739
156629551...

result:

ok 100000 lines

Test #4:

score: 0
Accepted
time: 205ms
memory: 3628kb

input:

100000
641009859 54748096
85739235 67050194 172255922
503158867 627937890
94015746 263268998 767974075
939887597 588586447
193971753 74870957 540012973
860350786 11308832
8059018 15147132 46269077
67590963 726478310
46505640 95785782 493390927
46718075 851555000
122848018 75433449 258721014
70635023...

output:

845015964
500313061
547414658
167346348
744068591
936854042
120534407
539004584
720547363
133185954
339273942
61486276
354909777
441032073
719710189
22459791
277981479
13206910
955330517
638502268
315407828
514965206
668963018
162557573
365255852
967113178
315192458
461064799
908195402
966384232
483...

result:

ok 100000 lines

Test #5:

score: 0
Accepted
time: 132ms
memory: 3700kb

input:

100000
1 1000000000
469813529 368130040 843594688
1000000000 1000000000
12405426 257556367 283770963
1 1000000000
23661960 384109268 851214918
1000000000 1000000000
23562630 46720955 334906549
1 1
99906836 38217992 425229411
1000000000 1
46505640 95785782 493390927
1 1000000000
48359252 92497933 403...

output:

433745965
563709738
636217684
559925373
678276102
775011524
715013066
223548864
662677489
886907569
917709024
239115936
38581913
468475426
193928268
926653428
110579445
987465383
996745956
647146676
726684395
733519290
319064716
1388472
172856225
75562413
511156850
945707859
438737613
58544558
59602...

result:

ok 100000 lines

Extra Test:

score: 0
Extra Test Passed