“范式杯”2023牛客暑期多校训练营1 - J - Roulette

Solost

2023 年 07 月 18 日

161 次浏览

暂无评论

340字数

题目题解

## 题目链接

[题目链接](https://ac.nowcoder.com/acm/contest/57355/J)

## 题目大意

有n元钱，要赚到m元。规则是第一局压1元，输了压之前压的2倍，否则继续压1元，输赢的概率都是0.5，问赢到m元的概率是多少

## 题解

以“输输输……输赢”为一个周期，可以赢到一块钱。因而需要经过 m 个这样的周期，有x元可以输，赚1块的次数是2^n - 1 <= x，n就是次数。然后我们一共有[n, n + m - 1]可以输，那么输x元赚1元的概率就是1-2^n，由于m很大，有一段区间内的概率是相等的，[2^n - 1, 2^(n + 1) - 2]是相等的，所以我们就可以一次算多个区间的概率

## 代码

```cpp
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f, mod = 998244353;
const int N = 2e5 + 10;

ll qmi(ll n, ll k, ll p = mod)
{
    ll res = 1 % p;
    while (k) {
        if (k & 1)
            res = res * n % p;
        n = n * n % p;
        k >>= 1;
    }
    return res;
}

void solve()
{
    ll n, m;
    cin >> n >> m;
    ll ans = 1;
    for (ll i = 1; (1ll << i) <= n + m; i++) {
        ll l = max((1ll << i) - 1ll, n), r = min((1ll << (i + 1)) - 2ll, n + m - 1);
        //从n开始花
        if (l > r)
            continue;
        ll p = (mod + 1 - qmi((1ll << i), mod - 2)) % mod;
        ans = ans * qmi(p, r - l + 1) % mod;//r-l+1代表有这么多个概率相同，所以用快速幂相乘
    }
    cout << ans << endl;
}
int main()
{
    // IOS;
    int _ = 1;
    // cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}
```

最后修改：2023 年 07 月 18 日