最近一直在摆，没有干什么正经事，还是挺愧疚的。
481 P8322 『JROI-4』少女幻葬
所有数除 \(k\) 变为要求相邻两项不互素，相邻三项 \(\gcd=1\)。
尝试列出 dp，令 \(f_{i,j,k}\) 表示考虑前 \(i\) 个数，后两项 \(\gcd=j\)，最后一项等于 \(k\) 的方案数。
根据 P7575 「PMOI-3」公约数 的经验，我们尝试分步进行转移，令 \(g_{i,j,k}\) 表示 \(\gcd(a_i,a_{i+1})=j,a_i=k\) 的方案数，那么只需不断进行 \(g\rightarrow f\rightarrow g\rightarrow f\rightarrow\cdots\) 的转移：
先考虑 \(g\rightarrow f\)，把式子列出来（忽略第一维）：
\[f_{i,j}=\sum_{\gcd(j,k)=i}g_{i,k} \]将 \(j,k\) 除以 \(i\) 后莫反，便可得到 dirichlet 前缀和的形式。
接下来考虑 \(f\rightarrow g\)，同样列出式子：
\[g_{i,j}=\sum_{\gcd(i,k)=1,k\mid j}f_{k,j} \]固定 \(j\)，那么我们需要对于 \(j\) 所有因子求出互素位置和，可以状压每个素因子的出现情况并做高维前缀和，这样转移一次是 \(O(m\log m+\sum_{i=1}^m\omega(i)2^{\omega(i)})\) 的。
整体复杂度 \(O(nm\log m(\log\log m+\operatorname{max\omega}(m)))\)，而且 \(\sum\omega(i)2^{\omega(i)}\) 的常数相当优秀。
482 HDU7199 Find the Number of Paths
题意可以转换为：
\[F_k(x)=\begin{cases}A(x)F_{k-1}(x)+F'_{k-1}(x)&k>0\\B(x)&k=0\end{cases} \]注意到两边配上 \(e^{\int A(x)\operatorname{dx}}\) 后可以统一两种转移，即令 \(G_k(x)=F_k(x)e^{\int A(x)\operatorname{dx}}\)，那么有：
\[G_k(x)=G_{k-1}'(x) \]于是本题在 \(O(n\log n)\) 内解决。
483 ARC137F Overlaps
法一：
不妨计数操作对应的括号序列数量，注意到一个合法括号序列应当对应 \(\prod(t_i+1)\) 种匹配关系，其中 \(t_i\) 为第 \(i\) 个右括号处的前缀和。
改为计数序列 \(t\) 的权值和，令 \(s_i=t_i+1\)，那么 \(s\) 需满足：
- \(s_i\geqslant s_{i-1}-1\)；
- \(1\leqslant s_i\leqslant k\)。
- \(s_n=1\)。
容斥第一种限制可以得到若干连续下降段，我们尝试计算一个连续段的生成函数——在值域上使用分治 NTT，并记录左右端点是否选择，合并是平凡的。
接下来需要合并连续下降段，只需满足 \(s_n=1\) 的限制，这并不困难。
复杂度 \(O(n\log^2 n)\)。
法二：
考虑容斥，为了钦定一个位置是最前的不合法位置，我们需要解决这样的问题“进行 \(n\) 次区间覆盖，以及 \(k\) 次后缀覆盖合法的概率”，设其为 \(f_n\)。
热身：使用 \(f_i\) 表示答案。
不合法的位置一定是某个区间左端点，那么区间可以分为：\(i\) 个严格在前面，\(1\) 个以其为起点，\(k\) 个严格跨过，\(n-k-i-1\) 个严格在后面（\(2\) 的次幂系数来源于确定区间是否受到过翻转）：
\[1-\sum_{i=0}^{n-k-1}{n\choose i,k,1,n-k-i-1}f_i2^{k+1}\frac{(k+2i)!(2n-k-2i-1)!}{(2n)!} \]接下来考虑怎么列出 \(f_i\) 的递推，仍然容斥一个更靠前的不合法位置，此时不合法的位置分两种情况——区间左端点，后缀左端点。
第一种情况（\(j\) 个区间严格在前面，\(1\) 个区间以其为起点，\(i\) 个区间跨过，\(n-i-j-1\) 个区间严格在后面；\(k-i\) 个后缀严格在前面，\(i\) 个后缀严格在后面）：
\[\sum_{i=0}^k\sum_{j=0}^{n-i-1}{k\choose i}{n\choose j,i,1,n-i-j-1}f_j2^{i+1}\frac{(k+2j)!(2n-2j-1)!}{(2n+k)!} \]第二种情况（\(j\) 个区间严格在前面，\(i\) 个区间跨过，\(n-i-j\) 个区间严格在后面；\(k-i\) 个后缀严格在前面，\(1\) 个后缀以其为起点，\(i-1\) 个后缀严格在后面）：
\[\sum_{i=1}^k\sum_{j=0}^{n-i}{k\choose i,1,k-1-i}{n\choose j,i,n-i-j}f_j2^i\frac{(k+2j)!(2n-2j-1)!}{(2n+k)!} \]（推式子时可以利用 \(\int_0^1x^a(1-x)^b\operatorname{dx}=\frac{a!b!}{(a+b+)!}\) 验证系数）
接下来整理式子：
\[f_i=1-\frac{1}{(2n+k)!}(\sum_{i=0}^k\sum_{j=0}^{n-i-1}{k\choose i}{n\choose j,i,1,n-i-j-1}f_j2^{i+1}(k+2j)!(2n-2j-1)!\\ +\sum_{i=1}^k\sum_{j=0}^{n-i}{k\choose i,1,k-1-i}{n\choose j,i,n-i-j}f_j2^i(k+2j)!(2n-2j-1)!)\\ =1-\frac{1}{(2n+k)!}\sum_{j=0}^{n-1}\frac{(k+2j)!(2n-2j-1)!}{(2n+k)!}{n\choose j}f_j(\sum_{i=0}^k{k\choose i}{n-j\choose i,1,n-i-j-1}2^{i+1}+\sum_{i=1}^k{k\choose i,1,k-1-i}{n-j\choose i}2^i)\]括号内仅与 \(n-j\) 相关，记作 \(g_{n-j}\)，其为卷积形式，容易求得。
接下来可以将式子化为 \(F(x)=H(x)-F(x)G(x)\) 形式，并多项式求逆求出所有 \(f\)，复杂度 \(O(n\log n)\)。
484 ARC146F Simple Solitaire
why qiuly so strong!!!
感觉这个做法挺人类的。
mex 在加元素过程中一般难以刻画，我们考虑倒序扫描序列维护 mex。容易列出一个朴素 dp，记录每天剩余的卡牌数量（即下标减 mex，可能有 \(\pm 1\) 的调整），可以得到这样的 dp 转移：
\[f_{i,j-1}\leftarrow j^2f_{i-1,j}\\f_{i,k}\leftarrow jf_{i-1,j}(k\leqslant j) \]转移形式很漂亮，我们不妨赋予其组合意义——将卡牌数量序列分割成若干连续下降段，两个相邻下降段需满足前者尾部不高于后者头部，每段的系数就是除结尾外卡牌数量平方的乘积乘上结尾的卡牌数量。
类似上一道题，容斥“前者尾部不高于后者头部”的限制，并尝试求出一个下降段（可以被分为若干连续下降段）的生成函数，以及以 \(1\) 结尾的下降段生成函数，合并是平凡的。
容易列出一个平方的 dp 求得该生成函数，注意到该 dp 等效于一些 \(2\times 2\) 矩阵的乘积，分治 NTT 即可，复杂度 \(O(n\log^2 n)\)。
485 ARC156E Non-Adjacent Matching
感觉不难。
如果没有最后一条限制，条件是经典的“最大值不超过总和一半，总和为偶数”。
最后一条限制可以考虑将 \(i,i+1\) 合并，不能产生自环，因此 \(\max X_i+X_{i\bmod n+1}\) 应不超过总和一半，充要性不难证明。
大于一半告诉我们不合法位置对数量不会超过两对，且两对时一定相交，于是我们可以统计所有情况并容斥去这两种情况。
前者较为简单，答案为（\(k_0\) 为 \(k-(k\bmod 2)\)）：
\[[x^{k_0}]\frac{(\frac{1-x^{m+1}}{1-x})^n}{1-x^2} \]提前处理出 \(\frac{1}{(1-x)^n(1-x)^2}\) 各项系数，计算时枚举上面选了多少个 \(x^{m+1}\) 即可（其实就是经典的不超过容斥）。
后者不妨枚举一对不合法位置计数，再减去两对不合法位置的方案数。
第一种情况，枚举这对位置的和，枚举其余位置的和，那么其余位置权值分配方案数只需容斥一次（这些位置总和显然不超过 \(2m\)），而枚举的位置分配方案数容易 \(O(1)\) 回答。
第二种情况，枚举中间位置的值，枚举其余位置的和（一定小于中间位置的值），给另外两个位置分配的方案数可以转化成一个二维前缀和，\(O(m^2)\) 预处理 \(O(1)\) 回答。
复杂度 \(O((n+m)m)\)。
486 AGC060E Number of Cycles
容易发现任意排列 \(b\) 的 \(f(b)+f(c)\) 奇偶性相同（一次 swap 两者均变化恰好 \(\pm 1\)），根据套路我们应求出 \(f(b)+f(c)\) 上下界，并尝试使用调整得到合法范围任意值的构造。
两者都不是那么显然，我们尝试猜测上下界的取值（通过打表之类的手段）：
上界为 \(f(a)+n\)，构造只需给出 \(b_i=i\)。注意到 \(f(c)\) 至多减少 \(1\)，因此在 \(f(b)\) 增加的过程中 \(f(b)+f(c)\) 不降，因此 \(f(b)=n\) 一定包含最优情况。
下界为 \(2\) 或 \(3\)，其为下界的原因显然，我们尝试构造达到下界的情况：
增量法，从前往后规划每个 \(b_i\) 的取值，我们维护已填入的前缀对应的两张排列的有向图（由有向环与有向链构成）。易知此时两张图连通块数量为 \(n-i+1\)，且每个连通块有恰好一个点能得到入边。
一个自然的贪心是尽量让连边不封闭成环，即我们不能连向 \(i\) 在排列 \(b\) 图中对应的连通块，以及在排列 \(c\) 图中对应的连通块，这一贪心在 \(i\leqslant n-2\) 时一定能找到符合条件的接入点，在 \(i=n-1\) 时能类似地保证增量不超过 \(1\)，那么一定能达到下界。
为了构造出中间的情况，我们可以借鉴上界的构造方式，以下界为起点，每次使 \(f(b)\) 加一，那么 \(f(b)+f(c)\) 不降，且在 \(O(n)\) 次操作内可以遍历下界到上界间所有合法状态。
\(f(c)\) 不好维护，但可以二分 \(f(b)\) 的取值，维护出 \(b\) 后线性求得 \(c\)，复杂度 \(O(n\log n)\)。
487 AGC060F Spanning Trees of Interval Graph
记总点数为 \(m\)。
前置知识：Matrix determinant lemma。
\[\det(D-G)=\det(D-UV^T)=\det(I_k-V^TD^{-1}U)\det(D) \]本题去除一行一列后转化为该问题，我们注意到 \(D\) 的行列式好求，我们可以尝试构造两个 \(m-1\times k\) 的矩阵 \(U,V\)，若 \(k\) 足够小，我们可以对右式采取 \(O(k^3)\) 的暴力消元求出行列式。
交集一定为区间，“交集不为空”的限制可以采用经典的点减边容斥，即：
\[\sum_{i\in I_1\and i\in I_2}1-\sum_{i,i+1\in I_1\and i,i+1\in I_2}1 \]容易由上式得到一个 \(k=2n-1\) 的构造，而求出 \(V^TD^{-1}U\) 各项并不难，枚举每行，之后每个区间产生的贡献容易使用前缀和计算，复杂度 \(O(n^3)\)。
标签：10,frac,log,sum,choose,2023,68,2n,2j From： https://www.cnblogs.com/xiaoziyao/p/17613000.html