稍后将会带来详细题解。
A 矩阵
随机一个向量乘到两边即可,错误率 \(\dfrac{1}{998244353}\)。
B 错排
组合意义 \(f_{i,j}\) 代表 \(i\) 个数没有限制,共有 \(j\) 个数求错排数。则 \(ans=P_{n-m}^{m}f_{m,n-m}\)。
不妨设没有限制得数为前 \(i\) 个数,后面 \(j-i\) 个数有限制,枚举第 \(i\) 个数是否等于 \(i\) 即可。
\[f_{i,j}=f_{i-1,j-1}+f_{i-1,j}\\ f_{i,j}=if_{i,j-1}+(j-i-1)(f_{i,j-2}+f_{i,j-1})\\ \]每 \(\sqrt{n}\) 行处理一整行,然后查询即为 \(\sum\limits_{i=0}^{m-p}\binom{m-p}{i}f_{p,n-m-i}\)。
C 异或图
容斥。
D 游戏
显然可以转化为找到一个点向不同子树延伸三条链,这是一个三维偏序问题,cdq 即可。
E 马戏团里你最忙
BM 算出递推式
F 树
转成bfs序,然后维护 “右链”
标签:偏序,限制,GDKOI2023,提高,个数,整行,即可 From: https://www.cnblogs.com/zcr-blog/p/17386628.html