QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#755329#9376. GameYipChip#ML 0ms3676kbC++231.1kb2024-11-16 17:04:332024-11-16 17:04:39

Judging History

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

  • [2024-11-16 17:04:39]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:3676kb
  • [2024-11-16 17:04:33]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
const int mod = 998244353;
typedef long long ll;
typedef pair<ll, ll> PII;
map<PII, ll> dp;

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

ll calc(ll x, ll y, ll p0, ll p1)
{
    if (x <= 0) return 0;
    if (y <= 0) return 1;
    if (dp.count({x, y})) return dp[{x, y}];
    ll p = p0 * calc(x, y - x, p0, p1) % mod;
    p += p1 * calc(x - y, y, p0, p1) % mod;
    p %= mod;
    dp[{x, y}] = p, dp[{y, x}] = (1 - p + mod) % mod;
    return p;
}

void solve()
{
    dp.clear();
    ll x, y;
    ll p1, p2, p;
    cin >> x >> y >> p1 >> p2 >> p;
    ll a = p1 * ksm(p1 + p2, mod - 2);
    ll b = p2 * ksm(p1 + p2, mod - 2);
    ll ans = calc(x, y, a, b);
    cout << ans << "\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T -- ) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: