总结
估：100 + 100 + 100 + 0
实：100 + 100 + 100 + 0 rk1
感谢 fsfdgdg 的麦当劳。/bx/bx/bx/bx
Max History
简化版题意：给定长度为 \(n\) 的数列 \(\{a_n\}\) ，定义数列的权值为 \(\sum^n_{i=1}[a_i>\max^{i-1}_{j=1}a_j]a_i\) ，询问该数列的所有 \(n!\) 种置换构成的数列权值和。答案对 \(10^9+7\) 取模。注意不算最大值的贡献.
考虑拆贡献到每一个数。假设大于等于 \(x\) 的数不包括自己有 \(cnt\) 个，那么我们算 \(cnt\) 排在 \(x\) 后面的方案数，那么我们一个一个加，加的第 \(i\) 个只能在可以插的 \(i + 1\) 个空中选后 \(i\) 个，那么显然有方案数：
那么设 \(x\) 有 \(c\) 个，那其贡献就应为 \(\frac {x \times c \times n!} {cnt + 1}\)。把每个数贡献加起来即可。做完了。
code
Wrong Answer on test 233 (Hard Version)
下文 \(a_{i + 1}\) 在 \(i = n\) 时均表示 \(a_{1}\)。我们发现具体的值是不重要的。设有 \(sum\) 个位置满足 \(a_i \ne a_{i + 1}\)，\(n - sum\) 个位置满足 \(a_i = a_{i + 1}\)。对于 \(a_i = a_{i + 1}\) 原序列 \(h_i\) 右移后不会造成得分的变化，随便选。对于 \(a_i \ne a_{i + 1}\) 若 \(h_i = a_{i + 1}\) 得分加一等于 \(a_i\) 得分减一，都不等于而为剩下的 \(k\) 个位置得分没影响，我们枚举 \(t\) 表示 \(t\) 个位置造成了得分的变化，有：
第二维 \(i\) 枚举的得分加一的位置。我们注意到 \(\sum_{i = \lfloor \frac t 2 \rfloor + 1} ^ t \binom{t}{i}\) 可以快速地求，当 \(t\) 为奇数显然为 \(2 ^ {t - 1}\)，偶数为 \(\frac {2 ^ t - \binom{t}{\lfloor \frac{t}{2} \rfloor}} 2\)。直接算就做完了。
code
Expected Components
简化版题意：定义长度为 \(n\) 的数列 \(\{a_n\}\) 的权值为 \(\sum^n_{i=1}[a_i\neq a_{i~\text{mod}~n+1}]\) ，定义数列 \(\{a_n\}\) 与数列 \(\{b_n\}\) 本质相同当且仅当两者能经过若干次循环位移后变得完全一致。给定长度为 \(n\) 的数列 \(\{a_n\}\) ，询问从该数列的所有 \(n!\) 种置换构成的所有本质不同数列中等概率随机选取一个，其权值的期望。答案对 \(998244353\) 取模。
code