字面意思。

恨妻不成7

传送门

前面的限制按照题意模拟即可，然后考虑维护平方和的常用手段：

本来是 \(\sum a^2\)，变成了 \(\sum (a+x)^2=\sum a^2+2ax+x^2=\sum a^2+2x\sum a +\sum x^2\)，发现维护一下“和”与“个数”即可。

完美数

传送门

首先有一个性质就是 \(\prod [a_i|n]=[\text{lcm}(a_1,a_2,\cdots,a_k)|n]\)。

意思就是要满足题面上的对任意一个都整除就等价于整除它们的 lcm。

那么发现所有的组合的 lcm 只有 48 种，这样模数就可以保存了。

现在又有一个性质：若 \(m1|m2\) 则有 \(a\bmod m1=(a\bmod m2)\bmod m1\)。

所以其实不用存余数，可以直接存对 \(\text{lcm}(1\sim9)=2520\) 取模的结果。

Umnozak

传送门

各个数位上的乘积种类不是特别多，大概就 \(36100\) 种，然后考虑暴力枚举每一种取值，发现一定能写成 \(2^{k_1}3^{k_2}5^{k_3}7^{k_4}\) 的形式（因为都是 \(1\sim 9\) 乘起来的），所以状态数不多，稍微剪一下枝。

完美消除

传送门

首先考虑什么时候能取到最小操作数：假设这个数是 \(\overline{a_na_{n-1}\dots a_{2}a_{1}}\)，考虑贪心，每次消除最长的一段相同的，不妨设这段是 \([l,r]\) 则把这一段变成 \(\max(a_{l-1},a_{r+1})\)。

考虑上述的贪心操作可以使用单调栈来维护，单调栈可以用一个大小为 \(2^9\) 的数来表示。

LIS数

传送门

考虑求 lis 的一种二分方法实际上是维护了一个元素不重（因为是严格上升的）序列，所以也可以用 \(2^9\) 的数压位，具体实现大概和“完美消除”差不多。

数对

传送门

考虑在位运算中高位的大小关系一定程度上决定了整个数的大小关系，所以可以像数位 dp 那样写，在做的过程中维护两个条件的成立与否即可。

Zhu的数学问题

传送门

和“数对”差不多，在针对于整数做加减法后虽然进退位的影响没有位运算那样大，但还是可以这么做，但是需要维护一下进退位的值，当上面传下来的大于等于 \(2\) 或者小于等于 \(-2\) 就可以直接不管了。

[SDOI2010]代码拍卖会

传送门

考虑把一个不下降的数拆成这样的形式：

\( 11111111111111111...11111+ \)

\( 111111...111+ \)

\( ... \)

发现这样可以算出每一种模数在长度为 \(1\sim n\) 之间的连续“11111”的出现次数（使用循环节），这样问题就变成了：有 \(p\) 种球，每种有不同的 \(g_i\) 个球，现在要从里面可重地选出 \(8\) 个（因为不能为 \(0\)，所以先加一个长度为 \(n\) 的“11111”），问组合数。就是一个简单的 dp 问题了。

最后考虑一个小问题：从 \(n\) 个球中可重地选 \(m\) 个进行组合，问方案数。

这个问题可以抽象为这 \(n\) 个球排成一排，有 \(m\) 个板子，假如第 \(j\) 个板子放在了第 \(i\) 个球的后面就表示选的第 \(j\) 个是 \(i\)，那么就变成了一个关于 \(n-1\) 个球分成可空的 \(m+1\) 组的方案数，就是 \(C_{(n-1)+(m+1)-1}^{(m+1)-1}=C_{n+m-1}^{m}\)。

【APIO2015】巴厘岛的雕塑

传送门

数据比较特殊，发现大致分为一下两种：

1. \(n\le 100\)

2. \(n\le 2000,A=1\)

考虑做一个贪心的操作从高位到低位确定答案在二进制表示下的所有位值。

不妨把答案设为一个 40 位的大整数，一开始是 \(2^{41}-1\)，假设现在正在枚举从低到高的第 \(i\) 位，已经确定了 \(i+1\sim 40\) 位的值，这时候可以先把这一位设为 \(0\)，看一下能否找到一种拆分方式使得每一段的和都被当前这个数包含（因为 \(1\sim i-1\) 都是 \(0\)，如果这样能满足那么答案一定是当前数的子集）。

考虑如何判断：其实就是一个简单的 dp，在 \(n\le 100\) 的情况下可以直接 \(O(\frac{n^3}{w})\) 做，而在 \(n\le 2000\) 的情况下相当于只需要最小的段数即可，可以 \(O(n^2)\)。

数数

传送门

首先考虑一个数 \(\overline{a_na_{n-1}\dots a_2a_1}\) 的贡献：\(\sum\limits_{i=1}\limits^{n}s_{i-1}a_i(n-i+1),s_n=\sum\limits_{i=0}\limits^{n}b^i\)。

设 \(f(l,r)\) 表示子串 \([l,r]\) 的贡献，\(k\) 表示 \(\sum\limits_{i=1}\limits^{n}f(i,n)\)。现在考虑在最高位增加一个数 \(a_{n+1}\) 产生的贡献：\(\sum\limits_{i=1}\limits^{n+1}f(i,n+1)=a_{n+1}+\sum\limits_{i=1}\limits^{n}\left(f(i,n)+b^{n-i+1}a_{n+1}\right)=k+s_na_{n+1}\)。

总之，就是 \(k'=k+s_na_{n+1},ans'=ans+k'\)。

发现只需要维护一下 \(k,ans\) 和数字个数就能 \(O(bn)\) 解决了。又发现除了取 \(0\) 和 \(up\)，其它的贡献可以一起算，复杂度变为 \(O(n)\)。

众数

传送门

考虑如何打暴力板子：直接传一个大小为 \(10\) 的数组表示当前所有数字出现的个数（不含前导 \(0\)），那么当 \(limit=lead=0\) 的时候，用 dp 算出剩下的的方案数，具体来说：设 \(f_{i,j}\) 表示前 \(i\) 种数（不含 \(d\)），放在了 \(j\) 个位置的方案数，有 \(f_{i,j}=\sum C_{j}^{k}f_{i-1,j-k}\)，注意需要枚举 \(d\) 在后面放多少个否则无法判断后面每一种数的放置个数上限。

【SDOI2013 R1 Day2】淘金

传送门

和“Umnozak”非常像，考虑用那题的方法算出每种 \(f(n)\) 的值所对应的值的个数，然后跑二路归并。