MC0357题解 | Decade

码蹄杯2024 MC0357-移动移动移动

问题描述

在一个二维坐标系中，有一个点一开始处在坐标 (x₁, y₁) 上，接下来该点会进行 n 次移动，每次移动有两种可能：

如果当前点坐标为 (x, y)，则下一步以的概率移动到 (x + 1, y)。
如果当前点坐标为 (x, y)，则下一步以的概率移动到 (x, y + 1)。

已知 p + q = 100。

现在问，经过 n 次移动后，该点恰好处在坐标 (x₂, y₂) 上的概率是多少？

可以证明概率可以表示为的形式，输出 x × y⁻¹ 对 998244353 取模的结果（y⁻¹ 满足 y × y⁻¹ ≡ 1 (mod 998244353)）。

输入格式

第一行包含一个整数 T (1 ≤ T ≤ 10³)，表示有 T 组测试用例。

接下来 T 行，每行 7 个整数 x₁, y₁, x₂, y₂, n, p, q (|x₁|,|y₁|,|x₂|,|y₂| ≤ 10⁹, 1 ≤ n ≤ 3 × 10⁵, 0 ≤ p, q ≤ 100, p + q = 100) 表示该组测试用例。

输出格式

对于每组测试用例，输出一个整数，表示答案。

样例输入

1
2
3

2
1 2 3 4 4 40 60
-5 3 -6 7 3 30 70

样例输出

1 2	923176378 0

思路

题目的最终要求就是在一个网格图上从点(x₁, y₁)移动到点(x₂, y₂)，并且移动过程中只能往左和往下。

因此最终往左移动的次数x就等于x₂ − x₁，往下移动的次数y就等于y₂ − y₁，且x + y = n。

所以接下来就是决定每一步到底往左还是往右，这就变为n个多重集合的全排列问题，方案数为：

但还要乘上往左和往右的概率，所以最终的概率为：在模M意义下有 P ≡ n! ⋅ (x!)⁻¹ ⋅ (y!)⁻¹ ⋅ p^x ⋅ q^y ⋅ (100⁻¹)^x + y (mod M) 因为M等于质数，所以逆元不用写拓欧了，直接用费马小定理。

次幂部分用快速幂就行。

由于有多组测试用例，所以阶乘部分不能每次都遍历计算一下，需要全局计算好。

代码

const int N = 300010, MOD = 998244353;
int TEST, n, m, k, t;
ll nums[N];

ll qpow(ll a, ll b) {
    ll res = 1;
    for (;b;b >>= 1) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
    }
    return res;
}

void init() {
    nums[0] = nums[1] = 1;
    for (int i = 2;i < N;i++) nums[i] = nums[i - 1] * i % MOD;
}

void solve() {
    int x1, y1, x2, y2, p, q;
    cin >> x1 >> y1 >> x2 >> y2 >> n >> p >> q;
    int x = x2 - x1, y = y2 - y1;
    if (x < 0 || y < 0 || x + y != n) {
        pl(0);
        return;
    }
    ll a = nums[n], b = nums[x], c = nums[y];
    ll ans = a * qpow(b, MOD - 2) % MOD;
    ans = ans * qpow(c, MOD - 2) % MOD;
    ans = ans * qpow(p, x) % MOD;
    ans = ans * qpow(q, y) % MOD;
    ans = ans * qpow(qpow(100, x), MOD - 2) % MOD;
    ans = ans * qpow(qpow(100, y), MOD - 2) % MOD;
    pl(ans);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    TEST = 1;
    init();
    cin >> TEST;
    for (int i = 0; i < TEST; i++) {
        solve();
    }
    return 0;
}

复杂度

时间：O(N + T ⋅ (log N + log M))
空间：O(N)