题解 | #Kevin翻硬币#

欢迎关注

珂朵莉 牛客周赛专栏

珂朵莉 牛客小白月赛专栏

D. Kevin翻硬币

比赛的时候，一直在猜结论，一共wa了17次，泪目。

但有一个想法，慢慢浮现出现来，比较硬核。

硬核解法

• 模拟 + 环形差分

先来说下模拟，实际上从原点出发，每次走k步，在环形的n中，一定可以回到原点的。最简单的验证，就是做n次的k步，必然回到原点。

更通俗的数学证明

kx = 0 mod n

gcd(k, n) | 0 必然成立，也就说 x 有解.

根据鹊巢原理，最多走n次，就能回到原点.

为了方便处理，我们把 1-index 转换为 0-index

那剩下的核心问题是：

如何判定是否能够翻转呢？

这个问题可以抽象为，从0点每次走k，然后回到0点的过程中，[0, n - 1]中的每个数的翻转次数都是奇数？ 那就一定可以。

假设当前点位t，翻转k，那相当于 [t, t + k - 1] 区间翻转次数整体+1

这里的一个难点，其实环形结构，如何处理这种跨区间的。

比如 [t, t + k - 1], t + k - 1 >= n - 1

那其实可分成两段[t, n - 1], [0, (t + k - 1) % n]做差分

这就是为什么说，环形结构的差分.

最后就是差分的常见累加计算，然后判定[0, n - 1]的数，改变次数都是奇数，那一定可行，否则不行。

import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt(), k = sc.nextInt();

            // 模拟 + 环形差分
            // 构建每次走k就行，难在于可行解的判定上
            int[] diff = new int[n + 1];
            List<Integer> res = new ArrayList<>();
            int x = 0;
            do {
                res.add(x);
                diff[x]++;
                if (x + k >= n) {
                    // 跨区间，就两段
                    diff[n]--;

                    diff[0]++;
                    diff[(x + k) % n]--;
                } else {
                    diff[x + k]--;
                }
                x = (x + k) % n;
            } while (x != 0);

            // 差分验证, 如果一个数的改变次数是偶数，则无解
            boolean f = true;
            int acc = 0;
            for (int i = 0; i < n; i++) {
                acc += diff[i];
                if (acc % 2 == 0) {
                    f = false;
                    break;
                }
            }

            if (!f) {
                System.out.println(-1);
            } else {
                System.out.println(res.size());
                System.out.println(res.stream().map(y -> String.valueOf(y + 1)).collect(Collectors.joining(" ")));
            }
        }
    }

}