CF1580 题解

第一场认真补完的 CF，题目真的很好。

CF1580A Portal

题意

给你一个 $n \times m$ 的 01 矩阵，你要修改其中最少的元素，使得存在一个长 $\ge 5$，宽 $\ge 4$ 的矩形满足：四个角不限定，边上是 $1$，中间是 $0$。$n,m \leq 400$。

题解

枚举矩形的左右边界，然后找一个最优的上下边界 $l,r$，问题转化为找 $\max\limits_{l\leq r} \{a_l+a_r+s_r - s_{l-1}\}$，维护前缀最值即可。

CF1580B Mathematics Curriculum

题意

求的长度为 $n$ 排列个数，满足此条件：恰有 $k$ 个数满足，所有包含这个数的区间中，不同的最大值的个数恰有 $m$ 个，$n \leq 100$。

题解

将「所有包含这个数的区间中，不同的最大值的个数恰有 $m$ 个」的数称作 $m$-好数，那么用 $f_{i,j,k}$ 表示：长度为 $i$ 的序列，$k$-好数有 $j$ 个的方案数。

考虑如何转移 $f_{i,j,k}$：枚举最大值的位置 $p$，左右两边只需要保留偏序关系，可以看作是长度为 $p-1$ 和 $i-p$ 的两个排列，划分方案数就是 $\dbinom{n-1}{p-1}$。

跨越最大值的区间显然只会对不同最大值个数有 $1$ 的贡献，需要找的其实是左右两边的 $(k-1)$-好数。所以可以再枚举一维 $c$ 表示左半边的 $(k-1)$ - 好数个数，右半边即为 $j-c-[k=1]$（中间的最大值是 $1$-好数，要判掉）。

所以有转移：

$f_{i,j,k}=\sum_p \binom{n-1}{p-1}\sum_c f_{p-1,c,k-1}\cdot f_{i-p,j-c-[k=1],k-1}$

时间复杂度 $O(n^5)$，但实际状态很少，可以通过。

CF1580C Train Maintenance

题意

有 $n$ 种列车，第 $i$ 种列车每工作 $x_i$ 天就要维护 $y_i$ 天。第 $1 \sim m$ 天中，每天加入一车或删除一车，并回答当前有多车在维修，$n,m \leq 2\times 10^5$。

题解

不难将题目转化为：将 $i \bmod p \in [l,r]$ 的 $a_i := a_i+1$，并单点查询。根号分治：

• $p> \sqrt m$ 的暴力，相当于要有 $O(m \sqrt m)$ 次区间加和 $O(m)$ 次单点求值，值域分块；
• $p \leq \sqrt m$ 的，维护一个 $s_{i,j}$ 表示 $\bmod i = j$ 的加了多少。

时间复杂度 $O(n+m\sqrt m)$。

CF1580D Subsequence

题意

给你一个长度为 $n$、互不相同的序列 $a$ 和一个数 $m$，需要选出 $m$ 个不同的数 $b_1, b_2, \ldots, b_m \in[1,n]$，最大化下式：

$m \sum_{i=1}^m a_{b_i} - \sum_{i=1}^m \sum_{j=1}^m f(b_i,b_j)$

其中 $f(l,r)$ 为 $a$ 的 $[l,r]$ 区间最小值（若 $l>r$ 则交换 $l,r$）。$m \leq n \leq 4000$。

题解

不难发现式子可以化为这样：

$\sum_{i=1}^m \sum_{j=i+1}^m a_{b_i} + a_{b_j} - 2f(b_i,b_j)$

观察到，若建出笛卡尔树，则 $f(b_i,b_j)$ 就是 $\mathrm{LCA}(b_i,b_j)$ 的深度，$a_{b_i} + a_{b_j} - 2f(b_i,b_j)$ 就是 $\mathrm{dis}(b_i,b_j)$。

故问题转化为，在带权的树上选出 $m$ 个点，两两距离最大，树上背包即可，复杂度 $O(nm)$。

CF1580E Railway Construction

题意

一个 $n$ 个点 $m$ 条边的有向正权图，你可以花费 $w_x$ 加入一条以 $x$ 为起点，终点与权值为任意的边（边权必须正整数）。需要使得对于任意的 $x\in [1,n]$，$1$ 到 $x$ 存在两条不交的最短路（不在 $1$ 或 $x$ 处有公共点），求最小花费。

有 $q$ 次修改，第 $i$ 次修改将 $w_{k_i} := w_{k_i} + v_i$，每次修改后需要输出最小花费，$n,q \leq 2\times 10^5$，$m \leq 3\times 10^5$。

题解

因为只有最短路相关的信息，故可以仅保留原图的最短路 DAG。同时，一条花钱加入的边 $x\to y$ 的权值一定是 $d_y - d_x$（$d_i$ 是 $1$ 到 $i$ 的最短路）。

然后考虑如何判定这个图是否合法：如果某个点只有一个入度，则一定不合法。所有点都有至少两个不同的入边（或者存在入边为 $1$），是否一定合法？下面我们归纳地构造一种方案。

将点按照 $d$ 升序考虑每个点。用归纳法的思想，不妨考虑到 $x$ 时，前面的点已经全部合法。任取 $x$ 的两个不同入边 $u,v$，并且任取一条 $1\to u$ 的路径 $S$（黑色路径），然后找出 $1\to v$ 的两条不交路径 $A$, $B$。如果 $\{A,B\}$ 中存在一条路径与 $S$ 不交，那就直接选不交的与 $S$；否则必然存在与 $S$ 的交点，我们找到 $d$ 最大的那个交点（黄点），并将其所属的路径的后半段改为 $S$ 的后半段即可，如下图。

这样就证明了图合法的充要条件：所有点都有至少两个不同的入边，或者存在入边为 $1$。也就是说，最优策略是将原图中只有一条入边的点 $u$ 拿出来，用 $d_x<d_u$ 且能让 $u$ 满足上述条件的最小的 $w_x$ 连这条边。

---

按照 $d$ 升序考虑每个点。我们维护前缀最小值 $f_i$ 与前缀次小值 $s_i$，易知 $i$ 的决策一定在这两个点当中。$w$ 在修改时只增不减很奇怪，考虑时间倒流变成只减不增，但最优决策之和似乎仍然难以维护。

我们先讨论平凡的情况，也就是修改的既不是 $f$ 也不是 $s$，相当于添加了一个数。把 $f,s$ 的图画成这个样子，其中横轴是按 $d$ 升序排序后的点，纵轴是值域，$\tt min$ 与 $\tt se$ 代表上述的最小值与次小值，黄线是添加的数 $x$。

受影响的区间有这两个：

• 在蓝色区间（$x\leq f$），我们会把 $s$ 用 $f$ 替换掉，然后把 $f$ 覆盖为 $x$。
• 在绿色区间（$f<x<s$），我们会把 $s$ 覆盖为 $x$。

观察这两个修改的性质，不难发现可以令总势能为 $f$ 与 $s$-连续段数量之和，不妨每次会遍历 $h$ 个 $s$-连续段，那么总势能一定下降 $h$。故连续段的合并/分裂/修改操作的次数是 $O(n+q)$ 的，所以考虑使用 set 维护连续段的暴力。并且我们惊喜地发现，对于 $f,s$ 都相等的一个连续段，计算其决策之和是非常容易的（查询区间内不与 $f$ 冲突的个数）。

加入特殊情况（修改的恰好是最小/次小值），这个均摊仍然满足吗？

• 修改次小值。显然，$s$-连续段的“断点”一定包含了 $f$ 的，故修改次小值只会出现在至多一个连续段，满足。
• 修改最小值。乍一看似乎不满足均摊，但这样的修改并不会影响冲突（因为只是改了权值，并没有改编号），所以另外开一棵线段树维护最小值即可。

这样就做完了这道题，时间复杂度 $O((n+m+q)\log n)$。

一点细节，可能存在 $d$ 相同的点，这也是我认为最难处理的地方。不难发现这个不会影响复杂度，但会让你调很久 TAT

CF1580F Problems for Codeforces

题意

求长度为 $n$，相邻两个数（包括 $1$ 和 $n$）之和 $<m$ 的序列个数，对 $998244353$ 取模，$n \leq 5\times 10^4$, $m \leq 10^9$。

题解

为方便表述，下文将用大写字母表示小写字母的 OGF，用 $m/2$ 替代 $\left\lfloor\dfrac{m}{2}\right\rfloor$。

将 $< \left\lceil\dfrac{m}{2}\right\rceil$ 的数叫做「小数」（用 $\tt S$ 表示），$\ge \left\lceil\dfrac{m}{2}\right\rceil$ 的数叫做「大数」（用 $\tt B$ 表示），那这个环有两种情况：

1. 被分成若干个 $\tt{SBS\dots BS}$（以 $\tt S$ 开头， 以 $\tt S$ 结尾，且 $\tt SB$ 交替）的「奇段」；
2. 整个环是 $\tt SB$ 交替的。

Part 1

先考虑第一种情况的计数，我们断环为链，统计由奇段拼成的链的个数。不妨长度为 $i$ 的奇段有 $a_i$ 种方案，用若干奇段拼成长度为 $i$ 的链有 $t_i$ 种方案，则考虑其 OGF 有 $T(x) = \dfrac{1}{1-A(x)}$。分两种讨论：

• 环的断点恰好是奇段的断点，此时环等同于链，方案数为 $t_n$；
• 否则我们枚举被断开的奇段的长度 $i$，方案数为 $(i-1)t_{n-i}a_i$。

故 $res=t_n + \sum (i-1)t_{n-i}a_i$，如何求 $a$？

称相邻两个数（不含 $1$ 和 $n$）之和 $<k$ 的序列为「$k$ 序列」，有个牛逼转化：将奇段的所有大数减去 $\left\lceil\dfrac{m}{2}\right\rceil$ 后，与所有的「$m/2$ 序列」一一对应。不妨加一维 $m$，$f_{m,i}$ 表示长为 $i$ 的「$m$ 序列」个数，$a_{m,i}$ 同理，则有 $a_{m,i} = f_{m/2,i}$（注意对 $a_{m,1}$ 并不适用），考虑求 $f$。

序列和环的不同点在于，序列的首尾不一定是奇段：可能是开头形如 $\tt{BSB\dots BS}$，中间一堆奇段，结尾形如 $\tt{SBS\dots SB}$ 的形式。我们把 $\tt{BSB\dots BS}$ 这种 $\tt B$ 开头 $\tt S$ 结尾，且 $\tt BS$ 交替的段叫「偶段」（特别地，偶段可以为空），则序列的组成一定是 偶段 + 若干奇段 + 反的偶段，这让我们想到 GF：不妨设长度为 $i$ 的偶段有 $b_i$ 种方案，则 $F(x) = \dfrac{B(x)^2}{1-A(x)}$。但它是错误的，漏掉了一种情况：$\tt BSB\dots SB$。对于这种情况，容易发现和奇段一一对应，所以 $F(x) = A(x)+\dfrac{B(x)^2}{1-A(x)}$。同样的，上面的牛逼转化对于偶段仍然适用，也就是 $b_{m,i} = f_{m/2,i}$，这样的话可以用 $F_{m/2}$ 推得 $A_m,B_m$，然后推得 $F_m$。

因为 $m$ 每次减半，所以 $F_i$ 只有 $O(\log m)$ 个，复杂度是 $O(n \log n \log m)$。

Part 2

整个环是 $\tt SB$ 交替的，这种情况只会出现在 $n$ 为偶数时。记 $g_k$ 表示长度为 $n$ 且 $m=k$ 时 $\tt SB$ 交替的序列个数，$ans_k$ 表示 $m=k$ 时的答案。

我们发现将所有大数减去 $\left\lceil\dfrac{m}{2}\right\rceil$ 后，就是一个规模为 $m/2$ 的子问题，所以考虑用 $ans_{m/2}$ 还原回 $g_k$ 的方式：奇数位 $+\left\lceil\dfrac{m}{2}\right\rceil$，或偶数位 $+\left\lceil\dfrac{m}{2}\right\rceil$，故 $g_m = 2\cdot ans_{m/2}$。结合 Part 1 求得的答案 $res_m$ 可以得到 $ans_m=res_m + g_m$，就以 $O(n \log n \log m)$ 的复杂度完成了这道题。

查看代码

#include<bits/stdc++.h>
#define pbk push_back
#define FOR(i,a,b) for(int i=a,i##i=b;i<=i##i;++i)
#define ROF(i,a,b) for(int i=a,i##i=b;i>=i##i;--i)
using namespace std;
const int N=524293,mod=998244353,G=3,iG=(mod+1)/3;
inline int qpow(int a,int b){
	int R=1;
	for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)R=1ll*R*a%mod;
	return R;
}
inline int inv(int x){return qpow(x,mod-2);}
inline void chg(int& x){if(x>=mod)x-=mod;}
int SZ,iSZ,R[N];
void init(int S){
    for(SZ=1;SZ<S;SZ<<=1);
    iSZ=qpow(SZ,mod-2);
    FOR(i,1,SZ-1)R[i]=(R[i>>1]>>1)|((i&1)*SZ>>1);
}
struct poly{
	int n;vector<int>a;
	int& operator[](int x){return a[x];}
	void siz(int x){a.resize(x,0);}
	poly fit(int x){return siz(n=x),*this;}
	poly(int x=1,int A=0){n=x,siz(x),a[0]=A;}
	void ntt(int f){
		siz(SZ);
		FOR(i,0,SZ-1)if(i>R[i])swap(a[i],a[R[i]]);
		for(int i=1;i<SZ;i<<=1){
			const int w=qpow(~f?G:iG,(mod-1)/i/2);
			for(int j=0;j<SZ;j+=i*2){
				for(int e=1,k=0;k<i;e=1ll*e*w%mod,++k){
					int &x=a[j|k],y=1ll*a[i|j|k]*e%mod;
					chg(a[i|j|k]=x-y+mod),chg(x+=y);
				}
			}
		}
		if(f==-1)FOR(i,0,SZ-1)a[i]=1ll*a[i]*iSZ%mod;
	}
};
void Inv(poly f,poly& g,int D){
	if(D==1)return void(g[0]=inv(f[0]));
	Inv(f,g,(D+1)>>1);
	f.fit(D),init(D*2);
	f.ntt(1),g.ntt(1);
	FOR(i,0,SZ-1)g[i]=(mod+2-1ll*f[i]*g[i]%mod)*g[i]%mod;
	g.ntt(-1),g.siz(D);
}
poly Inv(poly f){
	poly rs(f.n);
	return Inv(f,rs,f.n),rs;
}
poly operator+(poly x,poly y){
	if(x.n<y.n)swap(x,y);
	FOR(i,0,y.n-1)chg(x[i]+=y[i]);
	return x;
}
poly operator-(poly f){
	FOR(i,0,f.n-1)f[i]=mod-f[i];
	return f;
}
poly operator*(poly x,poly y){
	init(x.n+=y.n-1),x.ntt(1),y.ntt(1);
	FOR(i,0,SZ-1)x[i]=1ll*x[i]*y[i]%mod;
	return x.ntt(-1),x;
}
poly operator-(poly x,poly y){return x+(-y);}
int n,m,rs;
poly solve(int m){
	if(!m)return poly(n+1,1);
	poly F=solve(m/2),A(n+1),B(n+1,1);
	FOR(i,1,n)(i&1?A[i]:B[i])=F[i];
	A[1]=(m+1)/2;
	poly I=Inv(poly(1,1)-A);
	F=A+B*B*I,rs=n&1?I[n]:(2ll*rs+I[n])%mod;
	FOR(i,3,n)rs=(rs+(i-1ll)*I[n-i]%mod*A[i])%mod;
	return F.fit(n+1);
}
signed main(){
	scanf("%d%d",&n,&m);
	solve(m),printf("%d",rs);
	return 0;
}

总结

神题，神场，只能膜拜。

要是我退役之前能做出一道 E 或者 F 这样的题，就没有遗憾了。