题目链接
题目大意
牛牛所在的城市有一种新型病毒开始扩散。在一个二维平面坐标系上，有一个感染者在( 0 , 0 ) (0, 0)(0,0)的位置。从时刻0 00开始，每一个在( x , y ) (x, y)(x,y)的感染者都会让下一个时刻( x , y + 1 ) , ( x + 1 , y ) (x, y + 1), \ (x + 1, y)(x,y+1),(x+1,y)感染者数量增加1 11。
牛牛想知道，对于特殊的n nn个点( x , y ) (x, y)(x,y)，在时刻t tt感染者的数量。
数据范围
- 1 ≤ n ≤ 1 0 5 , 1 \leq n \leq 10^5,1≤n≤105,
- 0 ≤ x , y ≤ 1000 , 0 \leq x, y \leq 1000,0≤x,y≤1000,
- 0 ≤ t ≤ 5000. 0 \leq t \leq 5000.0≤t≤5000.
Solution
根据题意，我们可以设f ( t , x , y ) f(t, x, y)f(t,x,y)表示t tt时刻( x , y ) (x, y)(x,y)感染者的数量。
递推式
f ( t , x , y ) = f ( t − 1 , x , y ) + f ( t − 1 , x − 1 , y ) + f ( t − 1 , x , y − 1 ) . f(t, x, y) = f(t - 1, x, y) + f(t - 1, x - 1, y) + f(t - 1, x, y - 1).f(t,x,y)=f(t−1,x,y)+f(t−1,x−1,y)+f(t−1,x,y−1).
边界条件
f ( 0 , x , y ) = { 1 , ( x , y ) = ( 0 , 0 ) 0 , ( x , y ) ≠ ( 0 , 0 ) . f(0, x, y) = \begin{cases} 1,& (x, y) = (0, 0) \\ 0,& (x, y) \neq (0, 0). \end{cases}f(0,x,y)={1,0,(x,y)=(0,0)(x,y)=(0,0).
归纳法
下面证明( 1 ) (1)(1)成立
f ( t , x , y ) = ( t x ) ( t − x y ) . (1) f(t, x, y) = {t \choose x}{t - x \choose y}. \tag{1}f(t,x,y)=(xt)(yt−x).(1)
t = 0 t = 0t=0时显然成立。
设t = k t = kt=k时
f ( k , x , y ) = ( k x ) ( k − x y ) , f(k, x, y) = {k \choose x}{k - x \choose y},f(k,x,y)=(xk)(yk−x),
那么当t = k + 1 t = k + 1t=k+1时，
f ( k + 1 , x , y ) = f ( k , x , y ) + f ( k , x − 1 , y ) + f ( k , x , y − 1 ) = ( k x ) ( k − x y ) + ( k x − 1 ) ( k − x + 1 y ) + ( k x ) ( k − x y − 1 ) = k ! x ! y ! ( k − x − y ) ! + k ! ( x − 1 ) ! y ! ( k − x − y + 1 ) ! + k ! x ! ( y − 1 ) ! ( k − x − y + 1 ) ! = k ! ( ( k − x − y + 1 ) + x + y ) x ! y ! ( k − x − y + 1 ) ! = ( k + 1 ) ! x ! y ! ( k + 1 − x − y ) ! = ( k + 1 ) ! x ! ( k + 1 − x ) ! ⋅ ( k + 1 − x ) ! y ! ( k + 1 − x − y ) ! = ( k + 1 x ) ( k + 1 − x y ) . \begin{align*} f(k + 1, x, y) &= f(k, x, y) + f(k, x - 1, y) + f(k, x, y - 1) \\ &= {k \choose x}{k - x \choose y} + {k \choose x - 1}{k - x + 1 \choose y} + {k \choose x}{k - x \choose y - 1} \\ &= \frac{k!}{x!\ y!\ (k - x - y)!} + \frac{k!}{(x - 1)!\ y!\ (k - x - y + 1)!} + \frac{k!}{x!\ (y - 1)!\ (k - x - y + 1)!} \\ &= \frac{k!\ ((k - x - y + 1) + x + y)}{x!\ y!\ (k - x - y + 1)!} \\ &= \frac{(k + 1)!}{x!\ y!\ (k + 1 - x - y)!} \\ &= \frac{(k + 1)!}{x!\ (k + 1 - x)!}\cdot \frac{(k + 1 - x)!}{y!\ (k + 1 - x - y)!} \\ &= {k + 1 \choose x}{k + 1 - x \choose y}. \end{align*}f(k+1,x,y)=f(k,x,y)+f(k,x−1,y)+f(k,x,y−1)=(xk)(yk−x)+(x−1k)(yk−x+1)+(xk)(y−1k−x)=x!y!(k−x−y)!k!+(x−1)!y!(k−x−y+1)!k!+x!(y−1)!(k−x−y+1)!k!=x!y!(k−x−y+1)!k!((k−x−y+1)+x+y)=x!y!(k+1−x−y)!(k+1)!=x!(k+1−x)!(k+1)!⋅y!(k+1−x−y)!(k+1−x)!=(xk+1)(yk+1−x).
所以( 1 ) (1)(1)式成立。
时间复杂度O ( max ( t , x , y ) + n ) = O ( n ) O(\max(t, x, y) + n) = O(n)O(max(t,x,y)+n)=O(n)
C++ Code
#include<bits/stdc++.h>usingi64=longlong;constexprintN=5000;constexprintP=998244353;std::array<int,N+1>fac{};std::array<int,N+1>inv{};std::array<int,N+1>ifac{};voidinit(){fac[0]=1;for(inti=1;i<=N;i++){fac[i]=1LL*fac[i-1]*i%P;}inv[0]=inv[1]=1;for(inti=2;i<=N;i++){inv[i]=1LL*(P-P/i)*inv[P%i]%P;}ifac[0]=ifac[1]=1;for(inti=2;i<=N;i++){ifac[i]=1LL*ifac[i-1]*inv[i]%P;}}intbinom(intn,intm){if(n<0orn<m){return0;}return1LL*fac[n]*ifac[m]%P*ifac[n-m]%P;}intmain(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);init();intn;std::cin>>n;for(inti=0;i<n;i++){intx,y,t;std::cin>>x>>y>>t;std::cout<<1LL*binom(t,x)*binom(t-x,y)%P<<"\n";}return0;}Appendix
代码中用到的组合数预处理仅在模数为质数的情况下用到，如模数不是质数，需要用递推式( 2 ) (2)(2)进行O ( n 2 ) O(n^2)O(n2)预处理。
( n m ) = ( n − 1 m ) + ( n − 1 m − 1 ) . (2) {n \choose m} = {n - 1 \choose m} + {n - 1 \choose m - 1}. \tag{2}(mn)=(mn−1)+(m−1n−1).(2)
代码中，fac \text{fac}fac表示阶乘，inv \text{inv}inv表示逆元，ifac \text{ifac}ifac表示阶乘的逆元。
关于逆元的O ( 1 ) O(1)O(1)求法，下面给出说明。
首先，特别规定0 − 1 = 1 − 1 = 1 0^{-1} = 1^{-1} = 10−1=1−1=1，方便后续处理和推导。
要求i ( i > 1 ) i\ (i > 1)i(i>1)在模P PP意义下的逆元，设P = k i + r ( 0 ≤ r < i ) P = ki + r\ (0 \leq r < i)P=ki+r(0≤r<i)，那么就有
k i + r ≡ 0 ( m o d P ) . ki + r \equiv 0 \pmod{P}.ki+r≡0(modP).
移项r rr得到
k i ≡ − r ( m o d P ) . ki \equiv -r \pmod{P}.ki≡−r(modP).
两边同时乘以r rr的逆元r − 1 r^{-1}r−1，再乘以− 1 -1−1，得到
− k r − 1 i ≡ 1 ( m o d P ) . -kr^{-1}i \equiv 1 \pmod{P}.−kr−1i≡1(modP).
两边同时乘以i ii的逆元 $i^{-1}，得到
− k r − 1 ≡ i − 1 ( m o d P ) . -kr^{-1} \equiv i^{-1} \pmod{P}.−kr−1≡i−1(modP).
所以i ii的逆元i − 1 i^{-1}i−1为− k r − 1 ( m o d P ) -kr^{-1}\pmod{P}−kr−1(modP)，把k = ⌊ P i ⌋ k = \left\lfloor \dfrac{P}{i} \right\rfloork=⌊iP⌋和r = P mod i r = P \ \text{mod} \ ir=Pmodi代入得到
i − 1 ≡ − ⌊ P i ⌋ ( P mod i ) − 1 ( m o d P ) . i^{-1} \equiv -\left\lfloor \dfrac{P}{i} \right\rfloor (P \ \text{mod} \ i)^{-1} \pmod {P}.i−1≡−⌊iP⌋(Pmodi)−1(modP).
