题解 [牛客练习赛62 B] 病毒扩散
病毒扩散
https://ac.nowcoder.com/acm/contest/5205/B
题目描述
题目讲的很清楚,这里就不加赘述了。
正解
考虑病毒扩散的组合意义,把它转化成从 的方案数。
一个点它在一秒内可以进行以下三种操作。
不动
(往上走
(往右走
至于这样为啥是对的,自己感性理解一下吧,直接讲也不太好讲。
最后答案就是 。
upd : 证明
考虑暴力更新大小为 的矩阵的过程。
有 。
第一项其实就是在这一秒不动,然后第二项是在这一秒往上走,第三项是在这一秒往右边走,对应着上面说的三种操作。
后面答案为啥是那个组合数呢?
我们要求的东西其实是:在 秒内,走
次向上的,走
次向右的,那么这个组合数就自然是没有问题滴。
代码
#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; }