CF1845E Boxes and Balls
有一个观察是球不能穿过对方，那么初始的第 \(i\) 个球 最后结束时也得是第 \(i\) 个。
设初始每个球位置 \(a_1,a_2\dots a_t\)，最终位置 \(b_1,b_2\dots,b_t\)，那么最小移动步数 \(S=\sum|a_i-b_i|\)。
而 \(S\) 应满足 \(S\le k\) 且 \(S\equiv k \pmod{2}\)（因为可以对一个球反复横跳）。
考虑 \(dp[i][j][s]\) 表示前 \(i\) 个位置放了 \(j\) 个球，目前的最小移动步数和为 \(s\)。 \(i\) 这一维可以滚动掉，空间没问题了，时间 \(O(n^2k)\)，有点难蚌。
可以发现一个事情，如果前 \(i\) 个位置原来有 \(c_i\) 个球，最终有 \(y\) 个，那么至少的移动步数为 \((c_i-y)^2\)。比如 \(y<c_i\) 的时候，最后 \(c_i-y\) 个球排在区间的最后，然后一个一个搬出去，每个至少搬 \(c_i-y\) 步，总步数就是 \((c_i-y)^2\)。
所以对任意 \(dp[i][j][s]\)，都应该满足 \((c_i-j)^2\le k\)，那么 \(|c_i-j|\le \sqrt{k}\)。
也就是说，只有 \(j\in[c_i-\sqrt{k},c_i+\sqrt{k}]\) 的 \(j\) 才可能成立。
于是 \(j\) 这一维可以只用枚举 \([c_i-\sqrt{k},c_i+\sqrt{k}]\) 了，复杂度降至 \(O(nk\sqrt{k})\)。
CF1842G Tenzing and Random Operations
看错题了/qd
\zrdz/组合意义\zrdz/
假设位置 \(0\) 到 \(1\) 初始有 \(a_1\) 条道路，\(1\) 到 \(2\) 初始有 \(a_2\) 条道路，以此类推，那么 \(\prod a_i\) 就是从 \(0\) 到 \(n\) 的路径条数。
修改操作相当于在一个位置放一个工具，工具之间两两不同，走到这个位置时会捡起所有工具，然后走的时候可以选择不用或用一个工具增加 \(v\) 条路并走这 \(v\) 条路中的一条。
发现用过的不同工具数 \(\le n\)，记录 \(dp[i][j]\) 为到达 \(i\) 时，已经用过 \(j\) 个工具的方案数。
那么：
-
不用工具：\(dp[i][j]+=dp[i-1][j]\times a_i\)
-
用一个用过的工具：\(dp[i][j]+=dp[i-1][j]\times j\times v\)，这个 \(j\) 是因为用过的工具两两不同。
-
用一个没用过的工具：\(dp[i][j]+=dp[i-1][j-1]\times (m-j+1)\times i\times v\)，分别表示用剩下的哪一个、放在 \(1\) 到 \(i\) 哪个位置、\(v\) 条路径。
最后答案 \(=\dfrac{1}{n^m}\sum_{i=0}^ndp[n][i]\times n^{m-i}\)。这个 \(n^{m-i}\) 是因为还有 \(m-i\) 个工具没放，要算上这些的贡献。
CF1838E Count Supersequences
考虑每个 \(a_i\) 匹配最前面一个能匹配的 \(b_i\)，设 \(a_i\) 匹配 \(b_{p_i}\)，那么应该满足 \(\forall j\in [p_{i-1}+1,p_{i}-1],b_j\not = a_i\)，那么这些位置应该都只有 \(k-1\) 种选择。
而 \(p_n\) 后面的数就可以随便填了，每个位置 \(k\) 种选择。
枚举 \(p_n\) 可以得到一个正着做的式子 \(ans=\sum_{i=n}^m\binom{i-1}{n-1}(k-1)^{i-n}k^{m-i}\)，可惜优化空间太小了，可做但是困难。
考虑容斥，计算不满足条件的序列数量。枚举最多匹配 \(t\in[0,n-1]\) 位，那么\(p_t\) 后面所有位置不能是 \(a_{t+1}\)，那么除了已经确定的确定的位置都只能填 \(k-1\) 种，那么方案数就是 \(\binom{m}{t}(k-1)^{m-t}\)。
于是 \(ans=k^m-\sum_{t=0}^{n-1}\binom{m}{t}(k-1)^{m-t}\)。
标签：,那么,位置,sqrt,times,工具,dp From： https://www.cnblogs.com/jimmywang/p/17552327.html