哎

snow-panther / 2023-08-24 / 原文

哎

[NOIP2021] 数列

对于二进制进行 \(dp\)，考虑从低位向高位进行 \(dp\) 。

考虑到这样的难点在于进位，进位会对后面很多位都产生影响。
考虑如何消去这些影响，我们可以直接将影响存下来，也就是直接压进状态中。

设 \(f_{i,j,p,k}\) 表示二进制的第 \(i\) 位，后面对这位进了 \(j\) 位，用了 \(p\) 个位置，目前有 \(k\) 个 \(1\) 的方案的积之和。

有了这个定义转移就很简单了，考虑往后转移，将枚举相同的数放的个数即可，第 \(i\) 个数放了 \(g\) 个，则。

\[f_{i+1,{\lfloor \frac{j+g}{2} \rfloor},p+g,k+((j+g)\&1)} = f_{i,j,p,k}\times v_i^g\times\binom{n-p}{g} \]

时间复杂度 \(O(n^4m)\)

[CSP-S2019] Emiya 家今天的饭

将题目转化为有 \(n\) 行 \(m\) 列的表格，每行最多选 \(1\) 个，每列选的不能超过所选的一半。

注意到一半是一个很特别的东西，保证了如果有一列不合法，则最多只有一列不合法。

所以我们可以用所有方案数减去不合法的方案数。
枚举哪一列是不合法的，考虑我们要怎么统计。
注意到我们的一半是相对而言，和总选数有关，考虑到一列的方案数也不是之和个数有关，没办法简单地进行单独处理。
所以考虑压进状态中，\(f_{i,j,k}\) 表示前 \(i\) 行中，不合法的列中选了 \(j\) 个，其它的选了 \(k\) 个。
这样就很好地处理了，此时时间复杂度 \(O(nm^2)\)，注意到答案只和后两维的差有关，合并一下，将后面两维合并成差的一维即可。

时间复杂度 \(O(n^2m)\) 。

ARC104D Multiset Mean

感觉自己脑子爆了，想哭。

首先枚举平均数 \(x\)，将所有 \(a_i\) 变为 \(a_i-x\) 。
接着设计一个 \(dp\) ， \(f_{i,j}\) 表示前 \(i\) 个数，和为 \(j\) 的方案数。
容易发现答案为 \(f_{n,0}\)，这个暴力 \(dp\) 的时间复杂度是 \(O(n^4m^2)\)

考虑优化，我们注意到这样一个事情：

\[f_{i,j} = \sum f_{i-1,j-k\times a_i} \]

容易发现所有转移过来的状态的 \(j\) 都是模 \(a_i\) 意义下同余的，也就是说我们对于同余的数字快速做前缀和就好了。
这时时间复杂度 \(O(n^4k)\)，还是不太行。
考虑我们减去 \(x\) 的本质是什么，是将值域变为了 \([1-x,-1],[0,0],[1,n-x]\)，发现前面和后面的绝对值相同，所以只要 \(dp\) 预处理一下，然后把值域对应上去和相同的一乘就好了。
时间复杂度 \(O(n^3k)\)，感觉这题的难点就是前缀和优化和发现减 \(x\) 后值域没有本质的改变，正和负都是等价的。