一些题

· · 个人记录

一定会的

考虑时间倒流，此时每个时刻所覆盖的对应一段区间，每次就是向左/向右拓展，但是还是要记录状态，仍然是指数级，考虑原来表示的序列中的最长上升子序列必然能被表示出来，但是对 a_n 要特殊分讨，因此设出状态 f_{i,j,0/1} 为 [i,n] 中表示了 j 个，a_i 在左边，右边最小值/a_i 在右边，左边最大值。直接做是 O(n^2)，但是有经典结论随机排列的最长上升子序列长度期望为 O(\sqrt n)，所以状态数为 O(n\sqrt n)，考虑优化转移，原转移式是 f_{i,j+1,0}\leftarrow \min\{(\min\limits_{k>i,a_k>a_i} f_{k,j,0}),(\min_{k>i,f_{k,j,1}>a_i}a_k) \}\\ f_{i,j+1,1}\leftarrow \max \{(\max_{k>i,a_k<a_i} f_{i,k,1}),(\max_{k>i,f_{k,j,0}<a_i})\ a_k\}，容易发现是二维偏序形式，可以用树状数组优化，复杂度 O(n\sqrt n\log n)。

游走

伟大无需多言，首先有 f(x)=\sum\limits_{p_1,p_2,\dots,p_m,\sum ip_i=x} C_{t_0}^{p_1\ p_2\ \dots \ p_m\ t_0-\sum p_i} \prod C_{t_i}^{p_i}，若 p 对应方案数为奇数，由卢卡斯定理可得条件：p 是 t_0 的二进制划分，p_i 是 t_i 的二进制子集，直接考虑数不可取，不妨按位考虑，将 p 写成 30\times (m+1) 的矩形 G，若 G_{i,j}=1 当且仅当 j=0\vee 2^j\in t_i\& t_0，等价于每行取出一个 1，记每一行 1 的位置为 q_i，考虑 DP，记 f_{i,j} 为前 i 行，j 表示若 q_i=0,1,\dots,m 的奇偶性状态，DP 值表示满足此条件，前 i-1 行的疲劳值个数，可以直接 O(m^2) 转移，因此总复杂度为 O(2^mm^2\log t)。

毒

由 \gcd(a,b)=\gcd(a,b-a) 转化为求 T=\{S_{p_2}-S_{p_1},S_{p_3}-S_{p_2},\dots ,S_{p_k}-S_1,S_n\}，那么\gcd(T) 必然是 S_n 的因子，由于要求的是积，所以可以对于每个质因数分别算，不妨记 q_c\mid S_n，那么原式等价于 S_{p_1}\equiv S_{p_2} \equiv \dots \equiv S_{p_k}\ (\mod q^c)，考虑开桶统计 S_i\equiv x\ (\mod q^c) 的个数，对答案 k 的贡献为 q^{C_{cnt_x}^k} ，现在要求 C_n^m \mod 1e9+6，可分解成 (5e8+3)\times 2，单独处理质因子 2 即可。