[ACM]【找规律/排列组合】牛客练习赛62 病毒扩散

病毒扩散

传送门
题意：每个点在t时刻的值f[t][x][y]=f[t-1][x][y]+f[t-1][x-1][y]+f[t-1][x][y-1]，n次查找，输出。

思路：

这个真的推不出来啊…这里有大佬的感性认识及证明：其实就有点高中数学排列组合走迷宫内味：要到达（x,y），t时刻选择x+y个时刻走，然后再在这x+y个时刻中选择x个右行。
但我还是选择硬核找规律
先暴力打出结果，来找规律。可以发现，(x,y)点在t时刻的值为(t x)(t-x y)。于是打表求排列。
求排列有几种方法：
这位大佬总结得很好
（1）杨辉三角递推公式法
（2）乘法逆元
（3）Lucas定理
这里因为数据不大我也不会其他的于是选择了公式法。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=5003;
ll c[maxn][maxn]; //打表
//用普通求组合的操作就不能Mod了 
ll c2(ll n,ll m){
	if(m>n) return 0;
	if(n-m>m) m=n-m;
	ll ans=1;
	for(ll i=n;i>=m+1;i--) ans*=i;
	for(ll i=1;i<=(n-m);i++) ans/=i;
	return ans%mod;
}
void c1(){
	c[0][0]=1;
	for(int i=1;i<maxn;i++){
		c[i][0]=1;c[i][i]=1;
	}
	for(int i=1;i<maxn;i++){
		for(int j=1;j<=i-1;j++){
			c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
		}
	}
}
int main(){
	int ca;
	c1();
	scanf("%d",&ca);
	//千万小心越界 
	while(ca--){
		ll x,y,t;
		scanf("%lld%lld%lld",&x,&y,&t);
		if(t<x)printf("0\n");
		else printf("%lld\n",(c[t][x]*c[t-x][y])%mod);
	}
}