题解 [牛客练习赛62 B] 病毒扩散

病毒扩散

题目描述

题目讲的很清楚，这里就不加赘述了。

正解

考虑病毒扩散的组合意义，把它转化成从 $(0, 0) \to (x, y)$ 的方案数。

一个点它在一秒内可以进行以下三种操作。

不动
$(x, y) \to (x + 1, y)$ （往上走
$(x, y) \to (x, y + 1)$ （往右走

至于这样为啥是对的，自己感性理解一下吧，直接讲也不太好讲。

最后答案就是 $\binom t x \binom {t - x} {y}$ 。

upd : 证明

考虑暴力更新大小为 $n \times n$ 的矩阵的过程。

有 $f_{x,y} = f'_{x,y} + f'_{x - 1, y} + f'_{x, y - 1}$ 。

第一项其实就是在这一秒不动，然后第二项是在这一秒往上走，第三项是在这一秒往右边走，对应着上面说的三种操作。

后面答案为啥是那个组合数呢？

我们要求的东西其实是：在 $t$ 秒内，走 $x$ 次向上的，走 $y$ 次向右的，那么这个组合数就自然是没有问题滴。

代码

#include <bits/stdc++.h>
#define N 10000

using namespace std;

const int mod = 998244353;

int n;
int fac[N + 5], ifac[N + 5];

inline int read() {
    int x = 0; char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    return x;
}

inline int fpm(int x, int y) {
    int r = 1;
    while(y) {
        if(y & 1) r = 1LL * x * r % mod;
        x = 1LL * x * x % mod, y >>= 1;
    }
    return r;
}

inline int perm(int x, int y) { return 1LL * fac[x] * ifac[x - y] % mod; }
inline int comb(int x, int y) { return 1LL * perm(x, y) * ifac[y] % mod; }

int main() {
    fac[0] = 1;
    for(int i = 1; i <= N; ++i) fac[i] = 1LL * i * fac[i - 1] % mod;
    ifac[N] = fpm(fac[N], mod - 2);
    for(int i = N; i; --i) ifac[i - 1] = 1LL * i * ifac[i] % mod;

    n = read();
    for(int i = 1, x, y, t; i <= n; ++i) {
        x = read(), y = read(), t = read();
        if(x + y > t) {
            puts("0");
            continue;
        }

        int ans = 1LL * comb(t, x) * comb(t - x, y) % mod;
        printf("%d\n", ans);
    }
    return 0;
}