题目详情 - [Apio2016] 赛艇 - BZOJ by HydroOJ
-
看着个题目以为是变换考虑方向，但想了半天完全没有思路
-
先考虑暴力。设 \(dp_{i,j}\) 表示前 \(i\) 个数，第 \(i\) 个数强制选，值为 \(j\) 的方案数
-
容易得到转移方程：
\[dp_{i,j}= \begin{cases} \sum\limits_{k=0}^{i-1}\sum\limits_{l=1}^{j-1}dp_{k,l} & j\in[l_i,r_i] \\ 0 &otherwise \end{cases} \] -
这么做显然不行，因为值域太大了，状态根本列不下。考虑离散化。
-
我们先把闭区间变成左闭右开区间后离散化，记 \([b_i,b_{i+1})\) 为第 \(i\) 个区间，考虑改变 \(dp\) 状态的定义
-
设 \(dp_{i,j}\) 表示前 \(i\) 个数，第 \(i\) 个强制选，值在第 \(j\) 个区间内的方案数。转移时我们枚举第一个值在第 \(j-1\) 区间内的位置 \(k\) 即可转移。
-
如果你这么想你就太 naive 了！
-
我们发现我们完全没有考虑 \((k,i]\) 区间内的填数情况，这些区间里的数要么是在区间 \(j\) 中要么没有选，我们要考虑计算这里面的方案数。
-
引理：从 \([x,x+L-1]\) 这些数中选 \(n\) 个数，使得构造的序列非 \(0\) 位单增的方案数为 \(\binom{L+n}{n}\)
证明：如果没有选择非 \(0\) 位的条件的话方案数显然为 \(\binom{L}{n}\)，即从\(1,2,3,\cdots,L\) 中选 \(n\) 位即可。现在新增了选 \(0\) 的条件，我们不妨沿用插板法的思路，把原序列前添加上 \(n\) 位 \(0\)，此时如果选择了第 \(i\) 个 \(0\)，则等价于在第 \(i\) 位后面插入一个 \(0\) 。
-
有了这个定理，我们就可以列出转移方程：
\[dp_{i,j}= \begin{cases} \sum\limits_{k=0}^{i-1}\sum\limits_{l=1}^{j-1} \binom{L+m-1}{m}\times dp_{k,l} & j\in[l'_i,r'_i] \\ 0 &otherwise \end{cases} \]其中 \(L=b_{j+1}-b_j\)，\(m\) 表示 \((k,i]\) 中包含第 \(j\) 个区间的区间个数。组合数上标 \(-1\) 是因为我们强制第 \(i\) 位选。
-
这么做还不太够，因为暴力转移这个式子是 \(O(n^4)\) 的，发现我们可以用前缀和优化，最终可以做到 \(O(n^3)\)