2021 ICPC 上海站
链接
题解
B. Strange Permutations
一个长度为 $n$ 的置换形成了若干个有向环，那么在上面填排列后，环中边上相邻的点的数不能为 $i->i+1$。
直接枚举比较难，考虑容斥，记 $f(k)$ 表示选择了 $k$ 条边，使得每条边都满足 $i->i+1$ 的方案数，那么剩下 $n-k$ 个可以随便选，也就是 $(n-k)!$，答案就是 $\sum_{i=0}^n(-1)^if(i)(n-i)!$。
考虑 $f(i)$ 的求法，注意到一个整环不可能把所有边都选上以外，其他都可以。那么答案就是 $[x^i]\sum ((x+1)^{k_i}-x^{k_i})$。
分治FFT即可。
C. Strange Matrices
$n,m\le 8$，考虑轮廓线DP，对于每个点，会有三种状态：什么事都没有的，需要这一行给它的，需要同一列中的下面点给它的。那么DP时记录一下本行当前的状态，以及当前 $m$ 个数的状态就可以了。
时间复杂度 $O(nm3^{10})$。
D. Strange Fractions
可以发现，若 $(a,b)=1$，则 $(a^2+b^2,ab)=1$。那么 $p=a^2+b^2,q=ab$。随便做。
证明：$(a,b)=1$，则 $(a+b,a)=(a+b,b)=1$，则 $(a+b,ab)=1$，则 $(a^2+b^2,ab)=((a+b)^2,ab)=1$。
E. Strange Integers
排序以后贪心即可。
G. Edge Groups
简单树形DP。
H. Life is a Game
Kruskal重构树+树上倍增。
I. Steadily Growing Steam
简单DP，设 $f_{i,j,k}$ 表示处理到第 $i$ 个时，用了 $j$ 次，差值为 $k$ 的最大值。
J. Two Binary Strings Problem
记 $s_i$ 表示前缀和，$f(l,r)=1$ 当且仅当 $2s_r-r>2s_{l-1}-(l-1)$。
记 $t_i=2s_i-i$，按照 $t_i$ 排序，从小到大枚举，每次用bitset处理一下即可。
注意 $t_i=0$ 时的特判。
K. Circle of Life
打表找规律题。
M. Harmony in Harmony
神仙结论题，不太会…