2022/04/05 做题记录

AT3981

发现与 1 直接比赛的实际上有 n 组人中的最小值，每组分别有 $2^0$ 到 $2^{n-1}$ 个人并且在原序列上连续，考虑如果我们算出了每组的成员以及顺序的方案数，那么把 1 放在每个位置上都能唯一的确定这些组怎么放，于是将方案数乘上 $n$ 就是答案。

限制条件就是这些组的最小值不能在 A 内。

考虑容斥然后状压 dp，设 dp[s] 表示 s 内的组都已经计算完方案数并且钦定最小值在 A 内，可以发现 s 这个数的值正好是已经计算完方案数的人的数量（因为每组正好有 $2^0$ 到 $2^{n-1}$ 个人）。

从大到小枚举 A 的元素，转移时枚举把这个数作为钦定某个组的最小值或者不钦定到任何组，考虑枚举到 x 的时候任何比 x 小的元素都不会被钦定位置，于是容易计算 $\ge x$ 的数的个数，算个组合数就行。

答案就是 $\sum_S dp_S * (-1)^{\text{popcount}(S)}$

code: /code/2022.4.5/AT3981.cpp

bz2839

枚举交集然后二项式反演。

code: /code/2022.4.5/bz2839.cpp

CF666E

考虑建出广义 SAM，在 SAM 上线段树合并，那么在一个字符串对应的节点上线段树查询最大值和最大值位置就是答案，我们求出 S 的每个前缀在 SAM 里存在的最长后缀，也就是维护一个节点 x，如果能往 S 的下一位走就走，否则就跳 fail，同时维护当前节点对应串的长度，那么我们就能求出每个前缀的最长后缀的长度以及对应节点，然后询问时就看 r 这个位置的最长后缀到没到 l，如果到了在 fail 树上倍增找到最后一个 $len[x] \ge r-l+1$ 的点就行。

bfs 建广义 SAM 不需要特判。

注意如果答案是 0 输出 l 0。

code: /code/2022.4.5/CF666E.cpp

P2567

考虑幸运号码不多，可以全搜出来，然后考虑容斥，显然就是枚举若干个幸运数字的 lcm，然后把区间内的倍数个数乘上 $(-1)^{枚举的集合大小}$ 加到答案里，于是把幸运数组从大到小排序使得 lcm 尽快超出 r，直接暴力 dfs，实际跑的很快。

code: /code/2022.4.5/P2567.cpp

P2606

发现就是在一个二叉树内填数，保证每个子树根节点是子树内的最小值，直接树 dp，发现只要满足根节点是当前集合内的最小值剩下的两个子树可以随意分配，于是和集合内元素具体是什么无关，直接 dp[x] 表示 x 子树内填数的方案数，因为 m 可能小于 n 于是要卢卡斯。

code: /code/2022.4.5/P2606.cpp