这次比赛题目都超长,出题人太棒(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; //利用组合数公式,并将除法用逆元转换 } //函数区