LOJ tangjz的背包

题目大意

有 (n) 个物品, 第 (i) 个物品的体积为 (i)
令 (f(x)) 为选择 (m) 个物品, 体积和为 (x) 的方案数
令 (V = sum_{i=1}^m (n-i+1))
求 (f(1)cdots f(V)) 关于 (w=19190506) 的 (hash) 值
(1le mle n le 10^{12})

subtask 1

考虑递推
(f[n,m,x]) 是 ((a_1,cdots,a_m), a_ige 1, sum a_i = x) 的划分数量
我们让 (a_i -= 1) , 相当于物品大小变为 ([0,n-1]), 所需体积变成 (x-m)
枚举 (0) 号物品是否选择
就得到递推式 (f[n,m,x] = f[n-1,m,x-m] + f[n-1,m-1,x-m])

举个例子 (前两行平移了一下) :

f[3,1] =     (0,1,1,1,0,0)
f[3,2] =     (0,0,0,1,1,1)
f[4,2] = (0,0,0,1,1,2,1,1)

将第三维 (hash) 起来
那么 (f[n-1,m-1]) 那边需要补上后面的 (n-m) 个空位
而 (f[n-1,m]) 那边不需要

于是有 (f[n,m] = f[n-1,m] + f[n-1][m-1] w^{n-m})

subtask 2

搞搞生成函数什么的.

subtask 3

观察本题的递推式, 有 (downarrow), (searrow) 两种移动方式
每列只能用恰好一次 (searrow.~~) 确定好在哪里使用 (searrow) 就可以确定路径
给 (searrow) 标号. 设标号为 (i) 的 (searrow) 在第 (p_i) 行使用
我们要算的东西是: $$sum_{1le p_1lt p_2lt cdotslt p_mle n} frac{prod_{i=1}^m w^{{p_i}}{prod_{i=1}}m w^i}$$
考虑如下的变换 :
令 (p'_i = p_i - sum_{j<i} [p_j<p_i]). 可知 (1le p'_i le n-i+1).
而对于任一一组满足条件的 (p'), 每次让 (p_i) 选在剩余可选位置中第 (p') 个即可. 构成双射.
记 (sigma(p)) 表示 (p) 中的顺序对个数
那么 (prod w^{p'_i} = w^{-sigma(p)} prod w^{p_i})

令 (S) 为 (sum_{排列(置换)} w^{sigma})
我们对原式做一下变换

[egin{aligned} & sum_{1le p_1lt p_2lt cdotslt p_mle n\1le q_1lt q_2lt cdots lt q_m le m}frac{ prod w^{p_i} } { prod w^{q_i} } && 等价形式\ &= sum_{p, q} frac{ w^{sigma(p)} prod w^{p_i} } { w^{sigma(q)} prod w^{q_i} } && 上下同时乘S, 并将置换作用在p,q上\ &= sum_{p', q'} frac{ prod w^{p'_i} } { prod w^{q'_i} }\ &= frac{ prod_{i=1}^m (sum_{j=1}^{n-i+1} w^j) } { prod_{i=1}^m (sum_{j=1}^{m-i+1} w^j)} && 交换计算顺序\ &= frac{ prod_{i=1}^m (sum_{j=0}^{n-i} w^j) } { prod_{i=1}^m (sum_{j=0}^{m-i} w^j)} && 上下同时除w^m \ &= frac{ [n]^{underline m} } { [m]! } && [k] = frac{q^k-1}{q-1}(等比数列和)\ &= frac{ prod_{i=1}^m (q^{n-i+1}-1) } { prod_{i=1}^m (q^i-1) }\ end{aligned} ]

其实 (f[n,m] = {inom n m}_w)
关于本题递推式的更多信息可以参考wiki

subtask 4

先回顾 lucas 定理 : (inom n m equiv inom {lfloor frac n p floor}{lfloor frac m p floor} inom {nmod p}{mmod p} pmod p)
证明 :
(n!mod p = (prod_{i=1}^{lfloor frac n p floor} ip)~(prod_{i=1}^{p-1})^{lfloor frac n p floor}~(prod_{i=1}^{nmod p} i))
也即分成三个部分, 整除部分, 整块部分, 剩余部分
只有第一部分有 (p). 它可以写成 (p^{lfloor frac n p floor} lfloor frac n p floor !)
(1) (lfloor frac {n-m} p floor + lfloor frac m p floor < lfloor frac n p floor)
此时幂部分 (p) 有剩余, 阶乘部分剩余为整数, 无法将 (p) 抵消. 值为 (0)
对应的, 在lucas定理中, (nmod p + mmod p > p), 使得组合数值为 (0)
(2) (lfloor frac {n-m} p floor + lfloor frac m p floor = lfloor frac n p floor)
此时原式中的第一部分剩下的是组合数, 第二部分抵消, 第三部分不变.

这样不用生成函数来证明, 更容易推广一些

推广到这一题:
考虑令 (w^a-1equiv 0) 的最小的 (a)
记 (fac[n] = prod_{i=1}^n (q^i-1))
那么 (fac[n] = (prod_{i=1}^{lfloor frac n a floor}q^{ai}-1)~(prod_{i=1}^{n-1} q^i-1)^{lfloor frac n a floor}~(prod_{i=1}^{nmod a} q^i-1))
因式分解 (q^{ai}-1 = (q^a-1)(sum_{k=0}^{i-1}q^{ak}) = i(q^a-1))
因此 $fac[n] = (q^a-1){lfloor frac n p floor} lfloor frac n p floor! ( 剩下的推导就同理了, 最终得到: ){inom n m}_w = inom {lfloor frac n a floor}{lfloor frac m a floor} {inom {nmod a}{mmod a}}_w$