MtOI

非常好题目。DP 强行优化 \(O(n^3)\to O(n\log^2n)\)。实际上是把 \(O(nr)\) 和 \(O(nk)\) 的两个 Subtask 结合起来得到正解。 3 ......

记 $f_n$ 为 $k=0$ 的答案。则有答案为 $\binom n k ^2 2^k k! f_{n-k}$。接下来的问题变为怎样对每个 $n,k$ 求出 $f_{n-k}$。 **组合意义** 以下记 $\overline{A}$ 为 $A$ 的情侣。 欲求 $f_n$，不妨设第一排坐的两个人 ......

link：[P5516 [MtOI2019] 小铃的烦恼](https://www.luogu.com.cn/problem/P5516) ## 题意 给定 $n$ 个字符， 每次操作可以随机的选出两个字符 $S_a, S_b$ 使得 $S_a = S_b$， 问将所有字符变成相同字符所需要的期望步 ......

[洛谷传送门](https://www.luogu.com.cn/problem/P4931 "洛谷传送门") 设 $f_i$ 为 $i$ 对情侣完全错位的方案数，那么答案为： $$\binom{n}{k} \frac{n!}{(n - k)!} 2^k f_{n - k}$$ 分别代表选择 $k$ ......

不算堂堂的复活 原题链接 [P4921 [MtOI2018] 情侣？给我烧了！](https://www.luogu.com.cn/problem/P4921) # 思路 推导 / 二项式反演 + 生成函数 这个题看到恰好 $k$ 对其实很容易想到二项式反演，但是如果要推反演就需要很复杂的 GF 来 ......

# [MtOI2019]幽灵乐团 / 莫比乌斯反演基础练习题 ## 题目描述 东风谷 早苗(Kochiya Sanae)非常喜欢幽灵乐团的演奏，她想对她们的演奏评分。 因为幽灵乐团有 $3$ 个人，所以我们可以用 $3$ 个正整数 $A,B,C$ 来表示出乐团演奏的分数，她们的演奏分数可以表示为 $ ......

## 简要题意 计算 $$\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}\left(\frac{\text{lcm}(i,j)}{\gcd(i,k)}\right)^{f(type)}$$ 其中： $$\begin{aligned} f(0)&=1 \cr ......

## 题意 求下面表达式的值， $$\prod_{i=1}^{A} \prod_{j=1}^{B} \prod_{k=1}^{C} \left( \frac{lcm(i,j)}{gcd(i,k)} \right)^{f(type)} \pmod{p}$$ 其中，$type=\{0,1,2\}$，$f ......