这次比赛题目都超长,出题人太棒(hen)了。可以进链接看原题


题目概要

题目描述:
一个二维平面,从左下角开始病毒扩散,每一个时刻每个感染点可以传上右两个点,使其+1。
求某一点在某一时刻的感染数。

输入描述:
接下来n 行,每行三个非负整数xiyiti ,表示有一个特殊的点在 (xiyi),牛牛想知道在时刻 t这个点有多少感染者。
(1 ≤ ≤ 105≤ xiy≤ 1000,≤ t≤ 5000

输出描述:
对于每一个特殊的点,输出一行一个非负整数,表示在 t 时刻这个点的感染者数量,对 998244353 取模。


解析

首先,我们。。。来找规律吧。(先打个表看前几秒的情况)
  • 从这张图!大佬发现!(我没发现)这就是个杨辉三角(组合数)啊。(然后我发现,每行都可以提出来一组组合数。下面求解会用到)
但是只是发现这是一组杨辉三角,我还没发现什么用。这里就要借鉴我宝哥的智慧了!宝哥nb。见下图↓

但是从这里我们似乎也很难发现什么。那我们这样呢:
突然发现,行与列都有点关系!
  • 在提出来以后我们发现了一个很神奇的事情:每一行乘号左边的组合数和行数有关,而每一列右边的组合数却和时间有关(每一列在相同时间下都是同一组组合数)
  • 所以根据题目的x,y位置来确定就是:乘号左边的数为(与行有关),乘号右边的数为(与列有关)。

知道了咋整,就又到了快乐的写代码时刻了:
  1. 该输入的输入了,就开始我们的计算过程了。
  2. 接下来要进行一个判断,判断我们的坐标还有没有被感染到(也是防止组合数出现超范围的情况):x+y有最大值为t
  3. 接下来就是算乘号左值和乘号右值了:我们这里要用到组合数,运用组合数公式,我们要先得到阶层,再进行计算。
  4. 这里我们要用到我们学过的逆元知识(因为我们已经对阶层进行过取余,所以不能之间做除法了)将除法变为乘法(a/b=a*b的逆元)。
  5. 详细看代码哦~


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;
	//利用组合数公式,并将除法用逆元转换
}
//函数区