QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#581295#9376. GamecbbdhzML 0ms3544kbC++201.0kb2024-09-22 11:41:042024-09-22 11:41:04

Judging History

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

  • [2024-09-22 11:41:04]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:3544kb
  • [2024-09-22 11:41:04]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 998244353;
int qp(int a, int b, int mod)
{
	int ans = 1;
	while (b)
	{
		if (b & 1)
		{
			ans =(ll) ans * a%mod;
		}
		b >>= 1;
		a = (ll)a * a % mod;
	}
	return ans;
}
int dfs(int chou1, int chou2, int p1, int p2)
{
	
	if (chou1 <= 0)
	{
		return 0;
	}
	else if (chou2 <= 0)
	{
		return 1;
	}else {
		int temp= qp(p1 + p2, mod - 2, mod);
		int pa = (ll)p1 * temp%mod;
		int pb = (ll)p2 * temp % mod;
		int nm1 = gcd(chou1, chou2 - chou1);
		int nm2 = gcd(chou1 - chou2, chou2);
		return ((ll)pa* dfs(chou1/nm1, (chou2 - chou1)/nm1, p1, p2)%mod + (ll)pb * dfs((chou1 - chou2)/nm2, chou2/nm2, p1, p2)%mod)%mod;
	
	}
}
void solve()
{
	int a, b; cin >> a >> b;
	int temp = gcd(a, b);
	a /= temp; b /= temp;
	int x, y, z; cin >> x >> y >> z;
	cout << dfs(a, b, x, y) << endl;
}
signed main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	int T; cin >> T;
	while (T--)
	{
		solve();
	}
	


}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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
Memory Limit Exceeded

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:


result: