The 2021 ICPC Asia Shenyang Regional Contest 解题报告

先转化到，确定一个颜色序列，再选出一个子序列，颜色是按顺序出现的如 aaabbbbcdd 这样子，满足出现过的字符都出现了的前提下，先最大化第一种字符出现次数，再最大化第二种......

确定颜色序列而颜色数只有 \(20\)，所以想到状压 dp 令 \(f_S\) 表示填了 \(S\) 集合中的颜色，并且已经满足最大化的限制，当前选到了哪里。当它后面接了一个 \(c\) 之后我们需要保证在后缀中 \(U-S-\{c\}\) 都出现的前提下 \(c\) 尽可能多，所以对每个集合预处理出最靠后的后缀使得这个集合中颜色均出现，并预处理出子序列自动机即可得到 \(f_S\) 后面跟了一个 \(c\) 转移到的位置。

还要保证从前往后最大化出现次数，把集合大小 \(|S|=k\) 的放在一起，按照 \(k\) 从小往大去转移，这样对于每个 \(k\) 来说仅做出现次数最大的那些转移即可。现在时间复杂度是 \(\mathcal{O}(n|\Sigma|+2^{|\Sigma|}|\Sigma|)\)．

想得还挺顺利，一步步都想到了。

首先一个连通块的边数是偶数一定能全选完，这是一个经典的树上匹配问题，自底向上贪心选的时候先把挂在这个点上的所有边两两匹配完，如果匹配不完就留连到父亲的那条边就行。

现在 \(m\) 是奇数，如果删掉的边不是割边可以直接更新答案。然后发现割边不会删掉 \(>1\) ，若删掉了 \(A\to B\to C\) 中的两条割边形成了 \(A,B,C\) 这是三个连通块，其中 \(A,B,C\) 边数均为偶数，那么不删这两条割边会更优。于是枚举删掉哪条割边，判断是否满足条件满足条件就更新答案，这样就行了。

没救了。复数关于四则运算是封闭的，所以把一个复数看成一个未知数就行啊啊啊。既然保证有唯一解，那就尝试先设出来某个数是 \(0\) 还是 \(1\) 两种情况（如果是非 \(0\) 复数可以直接同时除掉它本身得到 \(1\)）然后前者可以直接求出来，后者三元三次方程就高消一下。

定位是简单题，但卡了许久。发现只和差有关所以做一遍 bfs 求出 \((0,0,0,0)\) 到所有状态的最小步数就行。

很快啊，一眼秒了。

问题就是计算完美匹配数，匹配要求在树上不能相邻。容斥钦定 \(k\) 相邻的，剩余的任意匹配方案数，乘上 \((-1)^k\) 贡献到答案里。于是 dp \(f_{x,i,0/1}\) 表示 \(x\) 子树内钦定了 \(i\) 对，其中 \(x\) 是否已被钦定，方案数是多少。树形背包复杂度 \(\mathcal{O}(n^2)\)．

可能真是做着做着累了就思考不动了。

尝试按字典序遍历出所有子串？endpos 相同的一个等价类里面的子串确实只有字典序最大的那个有用对吧。把 SAM 建出来，在 DAWG 上优先走较大的边去遍历 DAWG，打上它是被第几个遍历到的时间戳，如果有一个节点被遍历过了就不再走了。

确定前缀 \([1,i]\) 的答案的时候，它在 parent 树上的根链上最早被遍历到的串即为答案。

？这什么 shaber 板子题

先二分答案，然后分层图拆点跑最大流就行。

打牌分讨题。

copy 是能够复制 copy 的，所以有 water 并且 copy \(\geq 2\) 就能造成无限伤害。有水人的情况下 copy 复制成火球再把火球打出去能造成 \(1+1+2=4\) 点伤害。

策略是：

• 没有 waterman 在场上：一直留着牌直到有 water 就打 water，或者手里的 fire 和 copy 就能赢。
• 有 waterman 在场上：
  • water 和 fire 抽到直接打出去。
  • 有 2 张 copy 直接赢（手中的以及打出去的）
  • 有 1 张 copy：等到打过 fire 的时候再复制为 fire 打出去。

按照有无 water 分，假如枚举了 water 是在第几个抽到的，那么发现前半部分的信息只需得知是否有 fire，以及 copy 是 \(0/1/\geq 2\)；而后半部分的信息只需要得知当前 hp 剩余多少，fire 有无打过，copy 是手里 \(0\) 张 / 手里 \(1\) 张 / 已打过 \(1\) 张。

于是前半部分一个 dp 算，后半部分一个 dp 算，枚举第几个抽到 water 算下答案。还有一个问题是根本就不会进行到后半部分，一种情况是到 \(\left\lceil\frac{n}{2}\right\rceil\) 张抽完之后有 fire，由于 fire 和 copy 都能造成 2 的伤害所以直接赢；如果全是 copy，那么不断抽直到抽到 fire/water 就能赢，由于一次抽到 fire/water 的概率是 \(\frac{2}{3}\)，那么这里的期望步数就是 \(\frac{3}{2}\)．

具体细节就看看代码。

const int N=200010;
const int i3=332748118;
int f[N][2][3];//摸了n张牌, 0/>=1张fire, 0/1/>=2张copy
int g[N][2][3];//water打过, 怪物血量为k, 用了0/>=1张fire, 手里0张/手里1张/打出一张copy
int dfs(int k,int f,int c){
	if(k<=0)return 0;
	if(c==1&&k<=2)return 0;
	if(c==1&&f==1&&k<=4)return 0;
	if(~g[k][f][c])return g[k][f][c];
	int &now=g[k][f][c];now=1;
	//water
	cadd(now,1ll*i3*dfs(k-1,f,c)%mod);
	//fire
	if(c==1)cadd(now,1ll*i3*dfs(k-7,1,2)%mod);
	else cadd(now,1ll*i3*dfs(k-3,1,c)%mod);
	//copy
	if(c==0){
		if(f)cadd(now,1ll*i3*dfs(k-4,1,2)%mod);
		else cadd(now,1ll*i3*dfs(k,0,1)%mod);
	}
	return now;
}
int n;
signed main(){
	read(n);
	f[0][0][0]=1;
	for(int i=0;i<=(n+1)/2;i++)
		for(int j=0;j<=1;j++)
			for(int k=0;k<=2;k++){
				cadd(f[i+1][min(j+1,1)][k],1ll*i3*f[i][j][k]%mod);
				cadd(f[i+1][j][min(k+1,2)],1ll*i3*f[i][j][k]%mod);
			}
	int ans=0;
	memset(g,-1,sizeof(g));
	for(int i=0;i<=(n-1)/2;i++){//在i+1张牌抽到water
		cadd(ans,1ll*i3*f[i][0][0]%mod*(i+1+dfs(n,0,0))%mod);
		cadd(ans,1ll*i3*f[i][0][1]%mod*(i+1+dfs(n,0,1))%mod);
		cadd(ans,1ll*i3*f[i][0][2]%mod*(i+1)%mod);
		
		cadd(ans,1ll*i3*f[i][1][0]%mod*(i+1+dfs(n-3*i,1,0))%mod);
		cadd(ans,1ll*i3*f[i][1][1]%mod*(i+1+dfs(n-3*(i-1)-4,1,2))%mod);
		cadd(ans,1ll*i3*f[i][1][2]%mod*(i+1)%mod);
	}
	for(int i=0;i<3;i++){
		cadd(ans,1ll*f[(n+1)/2][0][i]*((n+1)/2+3ll*499122177%mod)%mod);
		cadd(ans,1ll*f[(n+1)/2][1][i]*((n+1)/2)%mod);
	}
	cout<<ans<<'\n';
	return 0;
}