Codeforces Round #768

A. And Matching

样例已知\(n=4,k=3\)无解.

首先直接配对就可以得到\(k=0\)的解.

注意到\(k<n\)如果\(k\neq n-1\), 直接将\(k\)和\(n-1\)配对, \(0\) 和\(n-k-1\)配对即可.

当\(k=n-1\)时, \((n-1,n-2)\ (1,3)\ (2,n-4)\ (0,n-3)\)可以解决问题.

D. Flipping Range

因为\(b_i\le n/2\), 通过叠加可以实现辗转相减. 于是考虑\(b=\gcd(B)\)即可.

当\(b\ge2\)时, 操作是不满秩的, 考虑非自由元部分, 每一个操作在消元后, 只会在前\([0,b-2]\)个位置里留下1个1, 或者全为1. 直接计算消除每一位上的1需要花费的最小价值.

计算答案时对全取正需要的操作消元后, 枚举是否全部异或上1, 根据非自由元的满足情况舍弃这些位置上的最小值即可.

E. Expected Components

利用Burnside引理分别计算component总数, 和本质不同的排列总数.

其中环上component等于相邻不同色的下标个数.

于是可以对每一个颜色二元组计算贡献.