题解：CF1615F LEGOndary Grandmaster

happybob · 2025-11-03 19:20:19 · 题解

此套路在不知道几场之前的梦熊模拟赛亦有记载。

将奇数位的权值 01 反转。注意到现在的操作变为了，每次交换相邻两个字符，问最少多少次达到目标。

记第一个串中 1 位置为 x_1<x_2<\cdots<x_k，第二个串中 1 位置为 y_1<y_2<\cdots<y_k，答案显然为 \sum \limits_{i=1}^k |x_i-y_i|。

枚举 x_i=a，y_i=b，计算第一个串 [1,a) 前缀和第二个串前缀 [1,b) 中 1 数量相等的方案数，后缀同理。即计算形如 \sum \limits_{i} \dbinom{n}{i} \dbinom{m}{i+k}，n,m,k 确定，将 \dbinom{n}{i} 变为 \dbinom{n}{n-i} 套用范德蒙德卷积即可。复杂度 O(n^2)。