养老记

· · 个人记录

洛谷，记录养老生活！

e了，不想写题。

CF1470E Strange Permutation

考虑到 c\leq 4 ，我们需要考虑这样的数量会很少。

我们设函数 F(i,c,k) 表示以 [i,n] 为后缀中操作次数上界为 c 的排名为 k 的操作区间中的第一个。

这咋求捏？

我们再设一个 S(i,c) 表示以 [i,n] 为后缀中操作次数上界为 c 的所有操作区间及其剩余次数的方案数 (l,r,w)

，这表示我在所有第一个操作区间为 (l,r) 的总操作共有 w 个。

我们把这些操作按照效果递增排序，设这个序列为 S(i,c)=\{(l_1,r_1,w_1),(l_2,r_2,w_2).....\}

于是我们的 F(i,c,k) 就可以表示为在 S(i,c) 中二分一个 t 使得 \sum_{i=1}^t w_i \ge k ，F(i,c,k)=(l_k,r_k)

考虑到如果我们能迅速求出 F(i,c,k) ，我们就可以依次确定每个操作对，得到答案。

但是如果要这样我们必须递推 F(i,c) 序列。

我们考虑从 F(i+1,c) 递推到 F(i,c) 最多增加 C 种类型，且每一种由于前缀确定一定在 F(i+1,c) 序列的最前端或者最后端。

然后直接逆着递推过来得到 F(1,c) ，顺便记一下 F(i,c) 在 F(1,c) 中的左右端点。

于是 O(nc^2+qclog(cn))

CF896E Welcome home, Chtholly

法一：

我们直接序列分块。

对一个块内建立 n 个值域点，用链表挂上其对应的位置。

考虑修改，对于散块重构（重新挂点），整块操作如下：

若 2x<\text{max} 我们把小于 x 的数暴力 +x ，并给整块 -x 的 \text{tag}。

若 2x\ge \max 我们把 >x 的数暴力 -x 。

以上两条均对挂着的链表整体移动，考虑其复杂度。

每次 2x<\text{max} 我们只对 [0,x] 内的位置进行链表移动，整块 \max -=x 花费了 O(x) 的操作量。

每次 2x\ge \max 我们对于 [x,\max] 内的位置进行链表移动，其中 \max \leq 2x ，因此整块 max -=x 花费了 O(x) 的操作量。

值域 O(n) ，有 O(\sqrt n) 个块，因此复杂度为 O(n\sqrt n) 。

法二：

摘自大姚姚。

对序列分块，每个块再设立 n 个值域点，设立阈值 B=\sqrt n

对于一次操作，散块暴力重构，只考虑整块操作：

若 x>B ，直接把所有位置挂着的链表暴力下移。

若 x<B ，考虑把 [B+1,2B] 内挂着的东西都搞到 [1,B] 内，对于 [B+1,n] 内所有值域点打一个整体下移的 tag。同时，当一个块累积的 tag>B 后会出现一个块实际位置在大于一个块下面去了，直接暴力下移。

考虑到一个值点最多下移 \frac{n}{B} 次，共有 O(n) 个可能存在的值点，复杂度 O(n \sqrt n)

CF1615D X(or)-mas Tree

我们发现一个事实，我们设 P(x)=\text{popcount}(x)\ \&\ 1 ，那么 P(x\ \text{xor}\ y)=P(x)\ \&\ P(y)

于是我们把已有的点权 v 变成 P(v)。

然后我们随便整一个哥们作为根，我们设每个点 u 到根的 \text{xor} 和为 f_u。

那么我们的 m 个限制变成 f_u\ \text{xor}\ f_v=0/1 。直接 \text{2-sat} 解出每个 f_u 的值。

然后差分异或一遍得出 \text{val}_u

CF1400F x-prime Substrings

我们发现一个惊人的事实，满足 x\leq 20 ，且满足题目条件的串数特别的少，把他们全部弄出来丢到 \text{AC} 自动机，我们只需要在 \text{AC} 自动机上跑个大 \text{DP} 。

CF1083C Max Mex

我们考虑如果存在一个 \text{mex}=x 的链，那么显然，权值处于 [0,x-1] 的点都在一坨。

我们考虑维护一棵线段树其第 [l,r] 位维护 [l,r] 权值的点是否能变成一条链，若是一条则同时维护其端点。

显然这很好合并和修改。

然后二分即可。

CF429E Points and Segments

我们不难建立一个上下界网络流模型：

先离散化，对于 i 向 i+1 连边。同时对于每组限制 [l,r] 我们对于 [l,r] 内每个点加一个度，并且连边 r+1 \to l,\text{flow}=1 。

然后假如一个点 i 度数 d 为奇数，连边 i\to i+1,\text{flow}=[\left\lfloor\frac{d}{2}\right\rfloor,\left\lceil\frac{d}{2}\right\rceil]。否则连边 i\to i+1,\text{flow}=\frac{d}{2}

显然跑一个上下界可行流输出方案即可。

如果你的网络流跑的比火箭快可以考虑。但是网络流是乌龟。

我们瞅一瞅这个模型，我们发现一个惊人的事实。

我们把 [l,r] 离散化后所在的段为 [L,R] 。我们对 L 和 R 连双向边，我们只要保证每个点 |in-out|\leq 1 即可。

但是不好搞，我们考虑把度数为奇数的点 i 向 i+1 连双向边（相当于加了一个 [i,i] 的涂色线段，这不影响构造方案和答案）。这样每个点度数都为偶数。

跑个欧拉回路即可。

CF1615H Reindeer Games

鲍旭回鬼板子老铁们！

[AGC005F] Many Easy Problems

考虑如何形式化地计算贡献，单独考虑一个块的贡献不好搞，考虑我们对于每个点为根，把他贡献到连通块里。我们记 siz_u[v] 表示以 u 为根的时候 v 的 \text{siz} 。

那么：

f(i)=\sum_{u}\left(\binom{n}{i}-\sum_{v\in son[u]}\binom{siz_u[v]}{i}\right)

只要这些点不在同一个子树内 u 一定会被记入答案，计算其方案数即可。

考虑我们换个东西枚举，枚举 siz_u[v] 的值 k 。记 g[k] 表示所有点作为根后其儿子 \text{siz}=k 的儿子个数总和。

那么：

f(i)+n\times\binom{n}{i} =\sum_{k}\binom{n}{k}\times g[k]

卷积即可。

[AGC001E] BBQ Hard

计算：

\sum_{i=1}^n\sum_{j=i+1}^m\binom{x_i+y_i+x_j+y_j}{x_i+x_j} n=2e5 \ \ |x_i|,|y_i|\leq 2e3

把 (x_i,y_i) 看作点的坐标，新建 n 个点放在第三象限 (-x_i,-y_i) 。那么问题变成了求所有三象限点到一象限点的距离和。

把它们放在平面上打一个 \text{tag}。一个二维 \text{DP} 即可。

于是复杂度 O(n+(4e3)^2)

[AGC019F] Yes or No

考虑策略，我们发现如果 n>m 我们一定回答 \text{YES}，反之 n<m 回答 \text{NO} 。

那么我们如果把 (n,m) 看作起点，其目标就是 (0,0) ，答案序列就是一条从 (0,0) 到 (n,m) 的折线，我们发现共有\binom{n+m}{n} 条。

我们发现如果在 (n,m) 前往 (0,0) 过程中，折线存在一个靠近 y=x 的小段，就多答对一道题。

但是如果过程中从 (k,k) 出发一定远离 y=x 且有 \frac{1}{2} 概率答对，这部分贡献先不管他。

那么其余部分的贡献，通过画图可知每一条折线贡献均为 \max (n,m) 。

考虑过 y=x 的某个点 (k,k) 对于所有折线的贡献总和。就是 \frac{1}{2}\times \binom{k+k}{k}\times \binom{n-k+m-k}{n-k}。

那么：

\text{ans}=\max (n,m)+\sum_{k=1}^{\min(n,m)}\frac{1}{2}\binom{k+k}{k}\binom{n-k+m-k}{n-k}/\binom{n+m}{n}

[AGC022F] Checkers

我们观察翻过去的特征，假设 A(x),B(y),C(z) ，我要把 A 连跨两人，翻 B 后坐标为 2y-x，翻 C 后坐标为 2z-(2y-x)。以此类推，我们发现每个中途点对于 \text{ans} 的贡献均为 c\times 2^{d},c\in{(1,-1)} 的形式。

我们建立以下模型，对于 A,B ，A 要翻过 B ，我们令 B\to A 连边，那么显然同一层的点贡献中的 2^d 均相同且为 2^{dep}。

由于坐标差距极大，我们答案其实就是每个点产生的 (c_i,d_i) 的不同组数。

考虑 c 的产生规律，假设一点 u 有 k 个儿子，对于所有儿子一定是依次先后操作的，容易发现存在一个儿子就会让其父亲的 c 变号。由于共有 \lfloor\frac{k}{2}\rfloor 个儿子操作后有奇数个剩下的儿子没有被操作，因此共有 \frac{k}{2} 个儿子传到父亲的 c 符号被取反奇数次，也就是一个点 u 有 \lfloor\frac{k_u}{2}\rfloor 个点符号与 u 相反。

考虑我们一层一层 dp ，设上一层有 j 个点有奇数个儿子，本层共有 k 个点，先忽略下一层对本层点的取反，那么本层中一共有 \frac{k-j}{2} 的点的 c 贡献与上一层其父异号。

接下来考虑下一层点对该层点的 c 取反，我们枚举实际上本层有 x 个点 c 与上一层其父亲 c 不同，这意味着，我们需要取反 |\frac{k-j}{2}-x| 个点，也就是我们强制这些点有奇数个儿子。

我们发现我们 dp 的时候并不关心上一层的点数以及当前是第几层的信息，我们只需要记录以前用了多少点，当前层点数，枚举 j,k,x 即可。不难得到转移：

f[i+k][\left|\frac{k-j}{2}-x\right|]=f[i][j]\times \binom{n-i}{k}\times \binom{k}{x}

[AGC020E] Encoding Subsets

哈哈题。

注意括号可以嵌套，先考虑只有一个外括号的问题，我们不妨设 f_{l,r} 表示把 [l,r] 区间进行合法编排的方案数，设 g_{l,r} 表示把 [l,r] 区间进行编排成为一个外括号的形式的方案数（(A\times n)），不难得到以下转移：

f_{l,r}=\sum_{k=l}^{r-1}g_{l,k}\times f_{k+1,r} g_{l,r}=\sum_{d|(r-l+1)}[\text{Can be divided into d same parts}]\times f_{l,l+d-1}

假如其他的 f,g 都算完了，算出 f_{l,r},g_{l,r} 复杂度都是 O(L) 的。

考虑怎么计算所有子集的答案。我们扩展定义 g_{l,r} 表示 [l,r] 所有子集的情况缩成一个括号的总方案数， f_{l,r} 定义类似。

那么显然我们在算 g 的时候，我们只需要在枚举 d 的时候我们默认这 \frac{L}{d} 个子串都是相等的，这意味着我们只需要对这 \frac{L}{d} 个子串取交集传给 F 进一步计算，这样能保证其所有子集都被算到了，也就是记忆化搜索。

考虑复杂度，我们设 T(n) 表示长度为 n 的串进行一轮 F,G 的搜索所用时间复杂度，不难得出：

T(n)=\sum_{i=1}^n(n-i+1)\times [1+\sum_{d|i}(i+T(d))] #### P3343 [ZJOI2015]地震后的幻想乡 我们现重申一下**概率分布密度函数**和**概率分布分布函数**，简称**概率密度函数**和**概率分布函数** 先介绍概率密度函数 $p(x)$，其满足： $$ \int _{-\infty}^{\infty} p(x)\text{dx}=1 $$ 可以按照离散概率密度函数进行理解，也就是各部分概率 $p(x)\text{dx}$ 加起来为 $1$。 同时概率分布函数的定义就是“前缀和”或者“后缀和“的形式： $$ P(y)=p(x\leq y)=\int _{-\infty}^{y} p(x)\text{dx} $$ 考虑期望的定义： $$ E(X)=\int _{-\infty}^{\infty} p(x)\text{dx}\times x $$ $$ =\int _{-\infty}^{\infty}p(x)\text{dx}\times \int _{-\infty}^{x}\text{dt} $$ $$ =\int _{-\infty}^{\infty}\text{dt}\int _{t}^\infty p(x)\text{dx} $$ $$ =\int _{-\infty }^{\infty} P(t)\text{dt} $$ 让我们进入本题，我们要求： $$ E(X)=\int _{0}^{1} P(t)\text{dt} $$ 我们设 $P_S(t)$ 表示我们只考虑 $S$ 内集合的概率分布函数在 $t$ 处的取值。这里定义为： $$ P_S(t)=\int _{t}^1 p(t)\text{dt} $$ 我们 #### [AGC020F] Arcs on a Circle 首先，我们确定一个事实。我们以长度最长的线段左侧作为端点，断环为链显然概率不变。此时若长度为 $L$ ，有 $n$ 条线段进行覆盖，那么这是个 $n$ 次多项式，$ans=f(m)$。 由于环长度为 $L$ ，覆盖线段的计量单位都为 $\frac{x_i}{L}$ ，我们直接代入 $x=c,2c.....(n+1)c$ ，函数值直接 $2^nx\ \text{dp}$ 即可。 考虑我们的答案是什么：$ans=\lim _{m\to \infty}\frac{f(m)}{m^n}$，显然我们只需要取 $[x^n]f(x)$ ，因为其他项都成为了低阶无穷大，贡献为 $0$。 但是有同志不会 $O(n^2)$ 插出系数。我们给予介绍： 拉格朗日： $$ \text{构造} f(z)=\sum_{i=0}^n\frac{y_i\prod_{j\not= i}(z-x_j)}{\prod_{j\not=i}(x_i-x_j)} $$ $$ \text{提取系数} a_i=\frac{y_i}{\prod_{j\not =i}(x_i-x_j)} $$ $$ \text{现在问题变成了上面那个} g(z)=\prod_{j\not=i}(z-x_i) $$ $$ \text{显然} f(z)=\sum_{i=1}^na_i\frac{g(z)}{z-x_i} $$ $$ \text{我们令}h(z)=\frac{g(z)}{z-c} $$ $$ [z^i]h=\frac{[z^i]g-[z^{i-1}]h}{-c} $$ 时间复杂度 $O(2^nn^4L^2)

[AGC021E] Ball Eat Chameleons

考虑对于一种顺序的球色，意味着我们需要尽可能浪费更少的红球。

不妨我们把红球，篮球分别平分成为 N 份。如果 R<B 一定不可行，如果 R>B+N 直接每个人多分红球即可。

当 B\leq R\leq B+N 我们存在 (R-B) 堆红球比篮球多 1 ，这些堆的球一定可行。

剩下的 N-(R-B) 堆必须要保证放最后一对红蓝球时一定要先放红球。

这也意味着，我们序列中必须存在 N-(R-B) 处不同的 RB 子序列。

我们考虑对于这个球序列的每个前缀，如果都满足 B_i-R_i\leq R-B ，那么一定可行。

如果我们把他们放在坐标轴上，R 表示向右走，B 表示向左走。

那么 ans 为从 (0,0) 走到 (R,B) ，并且不经过 y=x+R-B 即可。

用类卡特兰数解决，ans=\binom{R+B}{R}-\binom{R+B}{2R-N+1}。

于是枚举 R,B 计算贡献即可。时间复杂度 O(N)

[AGC021F] Trinity

这题一看，特别 \text{mur} ，怎么办？我们考虑一列一列加黑点，在确定 b,c 的时候考虑对于 a 数组的影响，

考虑我们设 f_{i,j} 表示我们已经填了 i 列，并且目前为止只有 j 个行存在黑点。

考虑我们如何转移，自然是 f_{i-1,j} \to f_{i,j+k} ，因为一次拓展多列并不好算。

现在分类讨论：

k=0:

$$ f_{i-1,j}\times \left(\binom{j}{0}+\binom{j}{1}+\binom{j}{2}\right)\to f_{i,j} $$ **k>0:** $k>0$ 意味着我们可以放黑点的位置一共有 $j+k$ 个，但是我们需要确定 $b,c$： 1. 假如我们 $b_i,c_i$ 均在新加的 $k$ 个位置之中，显然我们随便把一共的 $j+k$ 个行分 $k$ 个给第 $i$ 行就行了。 2. 假如我们只存在一个 $\max/\min$ 在这新增的 $k$ 个之中，我们的方案数显然是选出 $k$ 个分给第 $i$ 行，然后钦定一个 $\min/\max$ 在原有的 $j$ 个之中，这样的方案数是 $\binom{j+k}{k+1}$ ，显然我们要 $\times 2$ ，因为我们不知道是 $\max$ 还是 $\min$。 3. 假如俩都在里面，显然为 $\binom{j+k}{k+2}$ 。 通过计算，系数之和为 $\binom{j+k+2}{k+2} f_{i-1,j}\times \binom{j+k+2}{k+2}\to f_{i,j+k}

考虑到后一个转移是卷积形式，扔个 \text{ntt} 。

复杂度 O(nm\log n)。

O(n)-O(1) \gcd

给出 n ，要求能 O(1) 求出 \forall _{1\leq i\leq n} \gcd(i,n)，要求做到 O(n) 预处理， O(1) 回答询问。

首先我们设立阈值 T=\sqrt n ，我们预处理出 \gcd[1\to T][1\to T]，这部分直接转移：gcd[i][j]=gcd[j][i\mod j]。

接下来，我们考虑每个数字维护三个数字 s[i]=(a,b,c) 。满足 a,b,c<T 或者存在一个数是 >T 的质数。

我们公布程序流程，首先我们通过线性筛筛出每个数字的最小质因子 p 。

可以证明：对于 s(n/p)=(a,b,c) ，a,b,c 中一定存在一个数使其 \times p\leq T，下面开始证明。

于是，我们一定可以通过这种方式让每个数字表示成为 s(n)=(a,b,c) 的形式。

现在考虑如何计算 \gcd(i,n) 。如果 s(i) 有一只质数，显然 \text{ans}=p ，否则令 ans\times =\gcd(i,i\mod a),i=i\mod a，三个都做完即可，因为根号以下的 \gcd 已经处理完。

[AGC032E] Modulo Pairing

我们发现一个气人的事实，如果我们对数字排序，我们一定可以把序列分成两半，使得左半边大配小，右半边大配小。 \text{rt}

其中蓝色线表示两个数加起来 <\text{mod} ，红线加起来 >\text{mod} 。

在所有合法的位置之间，越靠左越小，并且我们需要保证右侧合法，这意味着我们需要找到最左的点使得右侧点能匹配。

直接二分即可。

[AGC032D] Rotation Sort

我们发现一个吓死人的事实，每个数我们只需要移动一次或者不移动，因为我们一定可以充当先知通过调整找到对应的位置。这意味着我们需要移动一些数字使得贡献总和最小。

考虑神秘性质，我们发现无需移动的的数字一定满足是一个原序列的上升子序列，我们考虑设 f_{i} 表示我们保持 i 作为子序列一员的时候 \text{ans} 的最小值。

考虑枚举上一个元素 j 进行转移，我们需要计算 [i,j] 之间数字比 a_j 小的贡献之和，比 a_i 小的贡献之和，这玩意随便预处理。

复杂度 O(n^2)

n 个 [0,1] 随机变量的 i 小值。

显然对于一个数 x ，随机变量 X<x 的概率就是 x ，比他大的概率就是 1-x。

观察 x 作为 n 个随机变量最大值的概率，一定为 x^{n-1} ，因为我们需要保证其余 n-1 个变量都 \leq x。

同理考虑我们最小值的概率为 (1-x)^{n-1}。

考虑直接列式子：

E(X)=\int _{0}^1 x^i(1-x)^{n-i}x\text{dx}

考虑分部乱搞：

\text{由} \int _{a}^buv'\text{dx}=uv|_a^b-\int_{a}^bu'v\text{dx} \text{我们不妨令} u=(1-x)^{n-i},v'=x^i \text{那么} =[(1-x)^{n-i}x^i]|_0^1-\int _{0}^1\frac{n-i}{i+1}x^{i+1}(1-x)^{n-i-1}\text{dx} =\frac{n-i}{i+1}\int_0^1x^{i+1}(1-x)^{n-i-1}\text{dx}

这与上形式类似，令：

a_i=\int_{0}^1 x^i(1-x)^{n-i}\text{dx} a_i=\frac{n-i}{i+1}a_{i+1},a_n=\frac{n}{n+1} a_i=\frac{i!(n-i)!}{(n+1)!} \text{ans}=a_i\times n\times \binom{n-i}{i-1}=\frac{i}{n+1}

[AGC032F] One Third

我们可以找到一个映射，相当于强制钦定 1,\frac{1}{3} 处有点，剩下再随机撒 n-1 个点的最小距离。具体看题解，

我们考虑如何求 [0,1] 撒点最小距离，我们设最短的为 x ，假如我们对于剩下的 n-1 个段都减掉 x ，着相当于映射为我们在 [0,1-nx] 随机选取 n-1 个点的最小值，即 P(L_{\min}\ge x)=(1-nx)^{n-1}。

我们考虑求期望：

E(L_{\min})=\int_{0}^{\frac{1}{n}}P(L_{\min}\ge x)\text{dx} =\int_{0}^{\frac{1}{n}}(1-nx)^{n-1}\text{dx} =\frac{\text{dx}}{\text{d}(1-nx)}\int_{0}^{\frac{1}{n}}(1-nx)^{n-1}\text{d}(1-nx) =-\frac{1}{n}\int_{0}^{\frac{1}{n}}(a-nx)^{n-1}\text{d}(1-nx) =-\frac{1}{n^2}\int_{0}^{\frac{1}{n}}(1-nx)^{n} =\frac{1}{n^2}

考虑次长不难得到：

E=\frac{1-nE(L_\text{min})}{(n-1)^2}+E(L_\text{min})=\frac{1}{n}(\frac{1}{n}+\frac{1}{n-1})

归纳得：

E_i=\frac{1}{n}\sum_{k=0}^{i-1}\frac{1}{n-k}

[AGC016E] Poor Turkeys

考虑到每一只火鸡的生存状况，在某一时刻我们对 (i,j) 进行了操作，如果我们最终要求 i 要存活，我们必须要保证此时刻之前 j 也要存活，否则 i 就要被迫被杀掉。因此我们考虑倒着维护一个存活包 S_i 表示我们如果要让 i 活下去，必须要让 S_i 内的点存活作为陪葬。

同时，对于一个操作 (i,j) 若 S_i \ and \ S_j \not = empty，那么 (i,j) 甚至拥有相同的陪葬品，注意到陪葬品只能用一次，因此也不合法。

考虑用 \text{bitset} 辅助实现。

[AGC016D] XOR Replace

你考虑啊，我们若把一个序列的异或和放在序列末尾作为 a_{n+1} ，不难发现把 a_i 替换为 \text{xor} 和的时候相当于我们把他和 a_{n+1} 交换值。

因此如果该序列可成功转换，当且仅当 a_{1}\to a_{n+1} 与 a_{1}\to b_{n+1} 排序后完全相同。

考虑需交换的两个值之间连边，显然答案就是交换次数（总边数） + 不同连通块数 -1，需要加上特判。对于每个连通块我们都需要先以 a_{n+1} 作为中转站再以 \text{siz}-1 的次数干掉一个连通块但是还要回到 a_{n+1} ，因此我们多了 \text{cnt}-1。

[AGC016F] Games on DAG

考虑一个图中两个点状态胜利当且仅当 SG_a=SG_b 也就是他们必须 SG 值相同。

考虑一个图中 SG 值相同的导出子图有什么特点。我们设这个集合为 T ，总点集为 S ，那么我们发现：

于是我们考虑枚举 S 集合内的 SG=0 的部分 T ，设 f_{S} 表示我们只考虑点集 S 时 1,2\ SG 值相同的方案数。

显然 1,2 需要同时在 T 或者 S-T 内，且 S 必须同时包含这两个点。

当然如果 1,2\in T 时，T 内部点随意向外连但必须有边，直接加上这个方案数因为 S-T 的 SG 值并不关心。

但如果 1,2\in S-T ，这意味着我们需要递归 f_{S-T} 进行求解。我们把导出子图 S-T 的所有点 SG 值都 -1 。这是一个等价的可递归问题。

时间复杂度 O(3^nn)

[AGC017F] Zigzag

我们考虑一条一条直线 dp ，我们只需要记录每个位置是往下跑还是右下跑，记录这个 01 状态，同时我们也需要记录当前我们填到了第 i 层，以及我们上一条直线的横坐标 x 。这样复杂度为 O(2^nn^2m) 会裂开。

现在我们考虑不这么做，我们并不必然需要记录上一条直线的坐标，我们只需要记录当前直线从 i 往后的最左直线形态，具体地如图：

我们对于上一条直线红线，这一条直线蓝线，我们如果记录绿线作为状态这是需要记录横坐标的，但是如果我们记录最左直线形态，我们只需要记录深绿色线就行了。

时间复杂度 O(nm2^n)

[ARC068D] Solitaire

容易发现双端队列一定从开头到 1 都是单调递减的，从 1 到末尾都是单调递增的。

但在出栈序列中，就是 a_1\to a_m 需要单调递减，但是从 a_{m+1}\to a_n 我们出栈的时候无所谓，哪边出都可以，如果我们钦定最后部分的顺序是单调递减的，我们只需要对这样的数列方案数 \times 2^{n-m-1}即可。

我们发现对于这样的序列，手玩即可发现，该序列一定是一个只存在至多两个下降子序列的排列，即不存在长度 >2 的上升子序列。同时 P_m=1 。我们称这样的序列是好的。

我们考虑一个排列的逆和该排列的关系，通过研究发现这两个序列要么同时是好的，要么同时是不好的。这容易手玩。

也就是说我们只需要计数所有 P_1=m 的好排列个数。最后答案 \times 2^{n-m-1}，

考虑我们设 f_{i,j} 表示我们拥有一个长度为 i 的序列，其 P_1=j。不难发现这容易 \text{dp} ，如下：

情况一

假如这个排列第一位为 n ，显然 n 并不参与任何连续长度为 3 的上升序列，我们只需要保证 a_2\to a_n 合法即可。

这意味着我们可以列出 \text{dp}

\sum_{1\leq j<i}f_{i-1,j}\to f_{i,i}

情况二

对于第一位 <n ，第二位 =n 的情况，显然 n 并不参与任何连续 3 升段。我们只需要把他丢掉，保证剩下部分不存在 3 升段即可。

f_{i-1,j}\to f_{i,j},j<i

情况三

图式情况中我们发现如果 a_1 在某个 3 升序列中，那么把 a_1 变成 a_2 也同样满足这是一个三升序列。也就是说 a_1 的存在并不影响整个序列是否是好的。我们不难得到：

\sum_{1\leq k\leq j}f_{i-1,k}\to f_{i,j}

总上我们三个转移式子通过整合得到，在 n>1 的情况下满足：

f_{i,i}=f_{i,i-1} f_{i,j}=f_{i-1,j}+f_{i,j-1},j<i

我们不难得到这玩意其实就是从 (2,1) 走到 (n,m) 并且不经过 y=x 的方案数。这种东西计算方式就是容斥掉经过 y=x+1 的部分。我们只需把 (n,m) 对 y=x+1 做一个对称即可。不难得到：

\text{ans}=\left(\binom{n+m-3}{n-2}-\binom{n+m-3}{n}\right)\times 2^{n-m-1}

[USACO22JAN] Tests for Haybales G

我们发现以下式子：

a_i\leq a_{i+1} a_{j[i]}\leq K+a_i a_{j[i]+1}>K+a_i

如果我们都把 i 向 j[i]+1 连边，并且把每一个点的儿子按照从小到大排序放出来的话，我们只需要满足以下的情况：

  1. 儿子的权值 c 严格满足 c+K<c_{fa}。
  2. 儿子 v 的父亲 u ，u 左侧的同层点 w 满足 a_w\leq a_u，右侧的同层点 \gamma 满足 a_\gamma >a_u。
  3. 儿子 v 的父亲 u 的左右同层点满足 a_v+K\ge a_w,a_\gamma <a_v+K

不难得到以下构造，我们求出每个点的 \text{dep}。按照从右到左访问儿子的顺序求出 \text{dfn}。构造 val_u=(n+1-dep_u)\times K-dfn[u]

这是一定满足以上三个条件的。

复杂度 O(n)

P5366 [SNOI2017]遗失的答案

考虑对于一个 \leq 10^8 的数字，他的最大质因子个数一定是 \leq 8 个的，并且满足只含有这些质因子的且 \leq 10^8 的数的个数一定是满足 \leq 10^3 的，这是可以打表得出的。

我们先求出每个质因子的上界和下界 \text{up,down}

我们不妨把这些可行的数字进行分类，我们用一个 16 位的二进制状态表示这个数字，若这个数字所含有的第 i 个质因子次幂为 c ，若 c=\text{down}_i 我们把 \text{sta}_{i+i-1} 设为 1，同理达到 \text{up} 的时候把 \text{sta}_{i+i} 设为 1。

我们的目标就是找出让这些 \text{sta} 并起来为全集的方案数。

我们考虑按照这个标准分类之后把对应位置数量 +1。对其作 \text{FWT} ，对每一个位求其 2^{f_i}-1 ，再差分回去。

于是我们可以得到造成并为全集的方案数。

由于我们只需要取在一处全集的点值。我们可以考虑暴力展开 \text{FWT} 。

\text{ans}=\sum_{S}(-1)^{all-|S|}(2^{cnt(S)}-1)

考虑一个修改只会对他的超集进行 cnt 的修改。

因此我们考虑直接枚举超集进行暴力计算。

考虑记忆化，复杂度最多 3^{16}。