51nod1838 Jabby的网格(二项式反演)

Author Avatar
Sakits 5月 06, 2018

题解

  感觉是两道二项式反演题拼在一起,虽然不会拼得像GDOI那样生硬…
  不按不合法方法走的方案数难算,所以考虑计算至少走kk次不合法方法的方案数FkF_k,然后用二项式反演求答案,FkF_k是可以算的。
  下面分成三个部分来搞搞。

Part 1

  令fi,x,yf_{i,x,y}为不考虑走法是否合法,走ii步走到(x,y)(x,y)的方案数。
  显然可以横纵坐标分开求,然后乘起来得到答案。
  问题可以转化成选ii0...Mx0...MxMyMy中的数,问和为xxyy的方案数。
  下面以横坐标为例:
  令AkA_k为有kk个超过限制的数的方案数,则有:

Ak=(ik)(xk×(Mx+1)+i1i1)A_k=\binom{i}{k}\binom{x-k\times(Mx+1)+i-1}{i-1}

  令BkB_k为恰好kk个超过限制的数的方案数,则有:

Ak=j=ki(jk)BjA_k=\sum_{j=k}^{i}\binom{j}{k}B_j

  二项式反演可得答案:

B0=j=0i(1)jAj=j=0i(1)j(ij)(xj×(Mx+1)+i1i1)\begin{aligned} B_0&=\sum_{j=0}^{i}(-1)^{j}A_j\\ &=\sum_{j=0}^{i}(-1)^j\binom{i}{j}\binom{x-j\times(Mx+1)+i-1}{i-1} \end{aligned}

  计算一个fi,x,yf_{i,x,y}的复杂度为O(R)O(R)

Part 2

  令gi,jg_{i,j}为用ii种不合法走法走到(Gj,Gj)(G*j,G*j)的方案数。
  这个直接用背包DP求就好了。
  复杂度O(K2X/G)O(K^2X/G)

Part 3

  令limit=min(Tx,Ty)Glimit=\frac{min(Tx, Ty)}{G}
  则有:

Fk=i=0limit(Rk)×fRk,TxG×i,TyG×i×gk,iF_k=\sum_{i=0}^{limit}\binom{R}{k}\times f_{R-k,Tx-G\times i,Ty-G\times i}\times g_{k,i}

  设GiG_i为恰好走了ii次不合法走法的方案数,则有:

Fk=i=kR(ik)GiF_k=\sum_{i=k}^{R}\binom{i}{k}G_i

  二项式反演可得答案:

G0=i=0R(1)iFi=i=0R(1)ij=0limit(Ri)×fRi,TxG×j,TyG×j×gi,j\begin{aligned} G_0&=\sum_{i=0}^{R}(-1)^{i}F_i\\ &=\sum_{i=0}^{R}(-1)^i\sum_{j=0}^{limit}\binom{R}{i}\times f_{R-i,Tx-G\times j,Ty-G\times j}\times g_{i,j} \end{aligned}

  复杂度O(R2X/G)O(R^2X/G),实际实现达不到这个复杂度,所以能够通过…