NC5205B 病毒扩散

Question

在一个二维平面坐标系上，有一个感染者在 $(0,0)$ 的位置。从时刻 $0$ 开始，每一个在 $(x,y)$ 的感染者都会让下一个时刻 $(x+1,y)$ ， $(x,y+1)$ 的感染者数量增加 $1$ 。

Solution

比赛的时候是打表+OEIS找规律出来的结果。
下面讲正解:
官方题解里说图片说明
然而我没有明白为什么可以这么转换，直到后来看了Lskkkno1写的证明才明白。
我们考虑地图和时间的关系，设 $f[x][y][t]$ 表示 $(x,y)$ 在 $t$ 时刻的感染者数量。

$(x,y)$ 在 $t$ 时刻感染者数量为：

$(x,y)$ 在 $t-1$ 时刻已有的量（不动）
$(x-1,y)$ 在 $t-1$ 时刻已有的量（往x方向走了一步）
$(x,y-1)$ 在 $t-1$ 时刻已有的量（往y方向走了一步）

$f[x][y][t]=f[x][y][t-1]+f[x-1][y][t-1]+f[x][y-1][t-1]$
然后这样子还是没法做的。这时候结合官方题解，把问题的模型转换为排列组合问题，答案就变成了 $C(t,x+y)C(x+y,x)=\frac {t!}{(t-x-y)!x!y!}$
我们预处理分子分母，预处理分母的时候还需要用到费马小定理将 $\frac {1}{x}\equiv x^{p-2}(mod\ p)$
复杂度 $O(2T+log(T))\approx O(T)$

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 998244353;
const ll  maxn = 1e6 + 5;
const int N = 5e3 + 5;

ll fac[N],ifac[N];

ll qpow(ll a,ll b){
    ll res=1;
    while(b>0){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

void init(){
    fac[0]=1;
    for(int i=1;i<=N;i++) fac[i]=fac[i-1]*i%mod;
    ifac[N-1]=qpow(fac[N-1],mod-2);
    for(int i=N-2;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    init();
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        int x,y,t;cin>>x>>y>>t;
        if(t<x+y) cout<<0<<'\n';
        else{
            cout<<fac[t]*ifac[t-x-y]%mod*ifac[x]%mod*ifac[y]%mod<<'\n';
        }
    }
    return 0;
}