Color Ball
给定 \(n\) 个筒，第 \(i\) 个筒装有颜色为 \(i\) 的球 \(a_i\) 个，重新排布这些球，使得每个筒中的球个数不变，且没有筒装有颜色与其编号相同的球，求排布方案数。不考虑同色球的差异，但是区分筒中求从下到上的排列顺序。
\(1 \le \sum a_i, n \le 2000\)
考虑直接容斥，设前 \(i\) 个筒，有 \(j\) 个球被放在不合法的位置，用 dp 算容斥系数与方案数的乘积即可。
[NordicOI 2017] Yule Lads
有 \(n\) 个人与 \(n\) 盏灯，初始状态都为开，人的编号分别为 \(1 \sim n\)，他们其中的 \(k\) 个人参与了按灯事件。
我们定义一次按灯事件为一个编号为 \(i\) 的人调整了所有编号为 \(i\) 的倍数的灯的开关状态（关变开，开变关）。
你知道 \(k\) 是多少吗？
\(1 \le n \le 10^{13}\)。
设按灯者集合为 \(S\)，则我们有：\(\varepsilon(i) = [i = 1] \equiv \displaystyle\sum _{j \in S, j|i} 1 \pmod 2\)。设 \(g_S(n) = [n \in S]\)，则 \(g_S * 1 \equiv \varepsilon \pmod {2}\)。
两边同时卷上 \(\mu\)，由莫比乌斯反演可以得到 $g_S \equiv \mu \pmod {2} $，所以说只需要求 \(\mu(i) \neq 0\) 的个数即可。考虑 \(\mu\) 的含义，容易转化为 \(1 \sim n\) 无平方因子的数的个数。枚举平方因子，套路地容斥计算：
[QOJ14414] Nice Subsequences
难度： 提高
给定长为 \(n\) 的序列 \(a\)，求其最长的子序列满足相邻项不互质，并求长度最大时，子序列的个数。
\(1 \le n \le 2 \times 10^5, 1 \le a_i \le 10^6\)
容易发现对于从 \(i\) 转移的时候，若 \(j < k\)，且 \(\gcd(a_i, a_j, a_k) = p\)，则直接先由 \(i\) 转移到 \(j\) 一定更有。考虑枚举 \(a_i\) 的每一个本质不同的质因子 \(p\)，连接边 \(i \to j\)，其中 \(j\) 是满足 \(j > i \land p\operatorname{|}a_j\) 的最小值。
然后跑 DAG 上 dp 就行了。
[QOJ18107] Parentheses
对于括号串的编辑如下：
- 选择区间 \([L, R]\)，反转后逐个翻转每个括号，例如左括号翻成右括号。
一个括号串的权值为最少编辑次数，使得括号串合法。对 \(0 \le i \le n\)，求长度为 \(n\) 且值为 \(i\) 的不同括号串总数 \(A_i\)，计算 \(\displaystyle\sum _{i=0}^n (i+1)A_i\) 的值。
\(n \le 10^6\)。
还是用一个经典的转换，设 ( 为 \(1\)，) 为 \(-1\)，求前缀和 \(s\)，要求 \(s_i \ge 0\)，且 \(s_n=0\)。
容易发现这个套路我们见过，但好像又不太一样，考虑这个编辑操作实际上是什么：
- 对于 \(i < l\)，没有影响，对于 \(i>r\)，都有 \(s_i \gets s_i +2(s_{l-1}-s_r)\)。
- 内部 \(l \le i \le r\)：反转+翻转操作等价于 \(s_{l+r-i} \gets s_{l-1}-(s_r-s_{l-1})+(s_{i-1}-s_{l-1}) = (s_{l-1}-s_r)+s_{i-1}\)。
相当于将 \([l, r-1]\) 反转后，对于 \(i \in [l, r-1]\) 的每个数加上 \((s_{l-1}-s_r)\)。
把问题画在图上（描点 \((i, s_i)\)），令 \(n\) 为偶数，容易发现：
-
操作为反转该段折线，并对齐到折线起点上。
-
第一种情况，无位置 \(s_i < 0\)，且 \(s_n=0\) 则值为 \(0\)。
-
第二种情况，无位置 \(s_i < 0\)，且 \(s_n>0\)，则值为 \(1\)。
设 \(s_n=d\)，构造方法是只需要找到高度差为 \(\dfrac{d}{2}\) 的 \(s_{l-1}, s_r\) 即可。令 \(r\) 为 \(n\)，一定能找到第一个 \(s_{l-1}=\dfrac{2}{n}\)，则其中间的 \(i \in [l,r]\) 都满足 \(s_i > \dfrac{d}{2}\)，所以反转后对齐，这一部分不会 \(<0\)。
-
第三种情况，存在位置 \(s_i < 0\)，怎么办，我们先找到最小的位置，记为 \(s_x\)，则：
由于 \(s_x\) 已经是最小的，且 \(s_0 = 0\)，找到 \(s_{l-1}-s_r=-s_x\) 是一定能够找到的。所以可以通过一次操作使 \(s_x' \ge -s_x\)，然后其余 \(< 0\) 的位置就可以通过 \(-s_x \ge -s_i\) 的原理，达到 \(\ge 0\) 的效果，可以一步操作，使这些位置均 \(\ge 0\)，且 \(s_n=0\).所以最多操作两次。而操作一次当且仅当 \(s_x\) 是所有 \(<0\) 中最靠右的，容易发现必然为 \(s_n\)。
简单统计即可。