目录
A
题面
题解
B
题面
题解
C
题面
题解
D
题面
题解
A
题面
一个 \(1\dots n\) 的排列 \(p\) 和一个 \(1\dots n-1\) 的排列 \(q\) 满足
对排列 \(I=1,2,\dots,n\) 进行 \(n-1\) 次交换：
交换 \(I[q[i]]\) 与 \(I[q[i]+1]\) .
做完操作后满足 \(I=p\) .
给定 \(p\)，计数 \(q\)，答案对 \(10^9+7\) 取模 .
题解
一个 \((q,q+1)\) 交换过后显然左右就不可能再交流了 .
于是每个区间的答案可以拆成俩区间，考虑区间 dp .
丢一下柿子，需要组合数学知识：
\[dp_{l,r} = \sum_k \dbinom{r-l-1}{k-l}\cdot dp_{l,k}\cdot dp_{k+1,r}
\]
B
题面
在 \(n\times n\) 每个方格上随机地填入 \(1\) 到 \(m\) 之间的正整数（每个方格填的数互不相同），然后随机地选出 \(k\) 个数字，把它们出现在棋盘上的方格涂黑 .
设有 \(R\) 行被整行涂黑，\(C\) 列被整列涂黑，则得到 \(2^{R+C}\) 分 .
求期望得分 .
题解
枚举 \(R,C\) 算概率 .
显然涂黑格子数为 \(x = Rn+Cn-RC\) .
算一个局面的超集概率是容易的 .
考虑 \(2^{R+C}\) 的组合意义，于是把所有概率加起来就凑出这个贡献了 .
大力算，概率是古典概型，俩组合数相除即可 .
upd. 社论
C
题面
原题
题解
中序遍历，最长不下降子序列 .
D
题面
一个序列 \(a\) .
一个区间 \([l,r]\) 是好的，当且仅当存在 \(k\in[l,r]\)，使得对于任意 \(i\in[l,r]\)，有 \(a_k \mid a_i\) .
求序列最长好子串 .
题解
这个条件等价于区间 \(\gcd\) 在区间中存在 .
俩 \(\log\) 解法比较好想，枚举左端点二分右端点即可 . 但这玩意涉及一个世界难题——判断数是否在区间中 .
于是考虑枚举 \(a_k\)，左右分别二分出最长子串，就是 \(1\) 个 \(\log\) 了 .
upd. 题解好像错了，st 表区间 \(\gcd\) 询问复杂度是带 \(\log\) 的，所以实际复杂度可能是小常数俩 \(\log\) .
Keven_He 你个暴力优化艹过去的不要评论了！！/fn
upd. 反转了，用三区间合并（Sqrt Tree）似乎可以靠谱一 \(\log\) .
upd. 可以记区间 \(\min\) 和区间 \(\gcd\) 然后随便二分做 .
st 表区间 \(\gcd\) 预处理复杂度是一个 \(\log\) 的证明可以看 OI-wiki .
