米哈游8.24第二题解析

    对于一堆的情况，找规律+数学归纳法易得若堆数是偶数，先手必赢，否则必输。因此多堆的话只看偶数堆就可以，如果轮到你场上没有偶数堆，你就似了。算一下偶数堆石子数直到除到奇数最多能除多少次2，作为每一堆的的状态g_i，易知奇数堆的g_i为0。如果轮到你的时候这些状态全是0，那你就似了。因为每个人都能拿n个，堆数可以被n整除，所以如果你拿2^k个，你就可以把这一堆的状态调整为g-k。这样问题就变成了有好几堆石子，每一堆个数分别为g_i，每局每个人能拿一堆里的任意颗石子。如果轮到你的时候没有石子，那你就似了。这种情况下后手只能让自己拿完那一堆的石子数和先手拿的那一堆的石子数一样，才有赢的可能。这样只需要把所有g_i异或，后手只能在异或结果为0时获胜，因为异或为0时后手拿完必定可以使非0堆的石子数全一样并且堆数为偶数，这样先手就似了。所以计算g_i，再异或，判断结果是否为0就可以。
    考试的时候我只想到统计偶数堆个数，判断个数是奇数还是偶数，只过了14%。之后跟gpt一块讨论，翻译gpt输出的抽象数学公式，才最终弄懂了这道题。#牛客AI配图神器#