服装页面设计的网站苏州城乡建设网站

服装页面设计的网站,苏州城乡建设网站,怎么建设小型网站,wordpress 4.6 注入题目链接 题目大意 牛牛所在的城市有一种新型病毒开始扩散。在一个二维平面坐标系上#xff0c;有一个感染者在 (0,0)(0, 0)(0,0) 的位置。从时刻 000 开始#xff0c;每一个在 (x,y)(x, y)(x,y) 的感染者都会让下一个时刻 (x,y1),(x1,y)(x, y 1), \ (x 1, y)(x,y1), (x1…题目链接题目大意牛牛所在的城市有一种新型病毒开始扩散。在一个二维平面坐标系上有一个感染者在( 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,y1),(x1,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 0t0时显然成立。设t k t ktk时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 1tk1时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(k1,x,y)​f(k,x,y)f(k,x−1,y)f(k,x,y−1)(xk​)(yk−x​)(x−1k​)(yk−x1​)(xk​)(y−1k−x​)x!y!(k−x−y)!k!​(x−1)!y!(k−x−y1)!k!​x!(y−1)!(k−x−y1)!k!​x!y!(k−x−y1)!k!((k−x−y1)xy)​x!y!(k1−x−y)!(k1)!​x!(k1−x)!(k1)!​⋅y!(k1−x−y)!(k1−x)!​(xk1​)(yk1−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#includebits/stdc.husingi64longlong;constexprintN5000;constexprintP998244353;std::arrayint,N1fac{};std::arrayint,N1inv{};std::arrayint,N1ifac{};voidinit(){fac[0]1;for(inti1;iN;i){fac[i]1LL*fac[i-1]*i%P;}inv[0]inv[1]1;for(inti2;iN;i){inv[i]1LL*(P-P/i)*inv[P%i]%P;}ifac[0]ifac[1]1;for(inti2;iN;i){ifac[i]1LL*ifac[i-1]*inv[i]%P;}}intbinom(intn,intm){if(n0ornm){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::cinn;for(inti0;in;i){intx,y,t;std::cinxyt;std::cout1LL*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−11−11方便后续处理和推导。要求i ( i 1 ) i\ (i 1)i(i1)在模P PP意义下的逆元设P k i r ( 0 ≤ r i ) P ki r\ (0 \leq r i)Pkir(0≤ri)那么就有k i r ≡ 0 ( m o d P ) . ki r \equiv 0 \pmod{P}.kir≡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} \ irPmodi代入得到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).