【牛客练习赛62】B-病毒扩散
病毒扩散
https://ac.nowcoder.com/acm/contest/5205/B
这次比赛题目都超长，出题人太棒（hen）了。可以进链接看原题
输出描述：
对于每一个特殊的点，输出一行一个非负整数，表示在 t 时刻这个点的感染者数量，对 998244353 取模。
题目概要
题目描述：
一个二维平面，从左下角开始病毒扩散，每一个时刻每个感染点可以传上右两个点，使其+1。
求某一点在某一时刻的感染数。
输入描述：
接下来n 行，每行三个非负整数xi，yi，ti ，表示有一个特殊的点在 (xi，yi)，牛牛想知道在时刻 ti 这个点有多少感染者。
（1 ≤ n ≤ 105，0 ≤ xi，yi ≤ 1000，0 ≤ ti ≤ 5000）
输出描述：
对于每一个特殊的点，输出一行一个非负整数，表示在 t 时刻这个点的感染者数量，对 998244353 取模。
解析
首先，我们。。。来找规律吧。（先打个表看前几秒的情况）
- 从这张图！大佬发现！（我没发现）这就是个杨辉三角（组合数）啊。（然后我发现，每行都可以提出来一组组合数。下面求解会用到）
但是只是发现这是一组杨辉三角，我还没发现什么用。这里就要借鉴我宝哥的智慧了！宝哥nb。见下图↓
但是从这里我们似乎也很难发现什么。那我们这样呢：
突然发现，行与列都有点关系！
- 在提出来以后我们发现了一个很神奇的事情：每一行乘号左边的组合数和行数有关，而每一列右边的组合数却和时间有关（每一列在相同时间下都是同一组组合数）
- 所以根据题目的x，y位置来确定就是：乘号左边的数为
（与行有关），乘号右边的数为
（与列有关）。
知道了咋整，就又到了快乐的写代码时刻了：
- 该输入的输入了，就开始我们的计算过程了。
- 接下来要进行一个判断，判断我们的坐标还有没有被感染到（也是防止组合数出现超范围的情况）：x+y有最大值为t。
- 接下来就是算乘号左值和乘号右值了：我们这里要用到组合数，运用组合数公式，我们要先得到阶层，再进行计算。
- 这里我们要用到我们学过的逆元知识（因为我们已经对阶层进行过取余，所以不能之间做除法了）将除法变为乘法（a/b=a*b的逆元）。
- 详细看代码哦~
AC代码
#include <iostream>
using namespace std;
typedef long long ll;
//代码预处理区
const int MAX = 1e5 + 10;
const int MOD = 998244353;
ll factorial[MAX];//保存阶层数
//全局变量区
template<class T>inline void read(T& res);//整型快读函数
ll qpow(ll a, ll b);//快速幂
ll C(ll n, ll m);//求系数
//函数预定义区
int main() {
factorial[1] = 1, factorial[0] = 1;
for (ll i = 2; i < MAX; i++)
factorial[i] = (factorial[i - 1] * i) % MOD;
ll n; read(n);
while (n--) {
ll x, y, t; read(x); read(y); read(t);
if (x + y > t) printf("0\n");
//x+y的最大值为一个定值，超过一定为0（未感染地区）
else {
ll left = C(t - y, x);
ll right = C(t, y);
//算出乘号的左值和右值
printf("%lld\n", left * right % MOD);
}
}
return 0;
}
template<class T>inline void read(T& res) {
char c; T flag = 1;
while ((c = getchar()) < '0' || c > '9')
if (c == '-')
flag = -1;
res = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
res = res * 10 + c - '0';
res *= flag;
}
ll qpow(ll n, ll m) {
ll ans = 1;
n = n % MOD;
while (m) {
if (m & 1) ans = ans * n % MOD;
m >>= 1;
n = n * n % MOD;
}
return ans;
}
ll C(ll n, ll m) {
return (factorial[n] * qpow(factorial[m] * factorial[n - m], MOD - 2)) % MOD;
//利用组合数公式，并将除法用逆元转换
}
//函数区 比赛 文章被收录于专栏
憨憨的专栏
查看14道真题和解析