QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#581287#9376. GamecbbdhzML 0ms3536kbC++201.3kb2024-09-22 11:34:262024-09-22 11:34:26

Judging History

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

  • [2024-09-22 11:34:26]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:3536kb
  • [2024-09-22 11:34:26]
  • 提交

answer

#include<bits/stdc++.h>
#define int 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 = ans * a%mod;
		}
		b >>= 1;
		a = a * a % mod;
	}
	return ans;
}
map<array<int, 2>, int>mmm;
int dfs(int chou1, int chou2, int p1, int p2)
{
	
	if (chou1 <= 0)
	{
		return 0;
	}
	else if (chou2 <= 0)
	{
		return 1;
	}
	else if (mmm.count({ chou1,chou2 }))
	{
		return mmm[{chou1, chou2}];
	}
	else {
		int temp= qp(p1 + p2, mod - 2, mod);
		int pa = p1 * temp%mod;
		int pb = p2 * temp % mod;
		int nm1 = gcd(chou1, chou2 - chou1);
		int nm2 = gcd(chou1 - chou2, chou2);
		mmm[{chou1, chou2}]=(pa* dfs(chou1/nm1, (chou2 - chou1)/nm1, p1, p2)%mod + pb * dfs((chou1 - chou2)/nm2, chou2/nm2, p1, p2)%mod)%mod;
		return mmm[{chou1, chou2}];
	}
}
void solve()
{
	mmm.clear();
	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()
{
	int T; cin >> T;
	while (T--)
	{
		solve();
	}
	/*int p1 = 2; int p2 = 8;
	cout << p1 << " " << p2 << endl;
	for (int i = 1; i <= 10; i++)for (int j = 1; j <= 10; j++)
	{
		cout << "A有筹码" << i << "   B有筹码" << j << "  " <<dfs(i,j,p1,p2)<<endl;
	}*/


}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: