2019牛客暑期多校训练营（第九场)
C. Inversions of all permutations
solved by rdc
题意 给序列，每种排列的贡献为 (b^{inv}) 。
做法
- 考虑每个元素不同的情况，从小到大，插入元素，枚举插入元素的位置，可实现递推。设 (f_i) 为 1 到 i 的排列的答案，(f_{i+1}=f_i(1+B+B^2+...B^i))
- 有元素相同呢？
- (frac{f_n}{prod_{i=1}^{mx} f_{c_i}}) 就是答案。
- 这是为什么啊？
- 【伪证】数学归纳，考虑 (a) 个 0，和 (b) 个 1 的排列得分[排骨龙]。
- 用 (E_x) 表示 (1) 到 (x) 排列得分的期望。
- 对于 1,2,3...a,a+1,...a+b 给前 (a) 个染上白色，后 (b) 个染上黑色，那么 (E_{a+b}=E_{a}E_{b}*(可达鸭))
- 可达鸭是啥？
- 是 “B 的 白和黑的逆序对个数 次幂”
- 为什么可以乘？
- 多个随机变量独立时，可以乘。
- 再一想，可达鸭不就是我们要求的东西吗？因此 (排骨龙=frac{f_{a+b}}{f_a*f_b})
E. All men are brothers
solved by rdc, 64 -2
题意 有多个加边操作，求两两不属于同一连通块的四元组。
做法 考虑加一条边，有多少种方案解体，解体的方案，设加的边两端分别在集合 (A,B) 那么解体的方案恰有一个点在 (A) 中，一个点在 (B) 中，剩下的两个点分立与不同连通块。并查集维护联通块 size 即可
解体 维护 size 写错了，WA 了两发
I. KM and M
upsolved
题意 计算 (sum_{k=1}^{n}[(km)&m])
做法
- 按位考虑贡献。
- 第 (B) 位对答案的贡献为，满足 (frac{km}{2^B}) 为奇数的 (k) 的个数，乘上，(2^B).
- 用 ([sum_{k=1}^{n}km\%2^{B+1}]-[sum_{k=1}^{n} km\%2^B]) 就等于上面那个东西，类欧经典问题。
- 为什么呢？画直线 (y=2^B,2*2^B,3*2^B,4*2^B.......)，考虑取模的几何意义。
复盘
- 比赛时施展了昨天多校学到的按前缀分类，预处理后缀。