5892. 石子游戏 IX (博弈)

因为胜负只与 3 3 3的倍数有关。

将所有石子 ( m o d 3 ) pmod 3 (mod3)。

先手只能选1或2石子。

分别考虑选1 或者选2是否能赢。

因为具有对称性，不妨考虑选1.

因为0对于和无影响。

所以我们在1，2之间考虑。

显然1之后只能跟1

1-1

两个1之后只能跟2

1-1-2

该2后面只能跟1

1-1-2-1

依次类推：1-1-2-1-2-1-2…

即：1 (12)^t

考虑进行最大的回合数： l e n = m i n ( c 1 , c 2 ) × 2 + c 0 + 1 len=min(c_1,c_2)times 2+c_0+1 len=min(c1​,c2​)×2+c0​+1

此时：先手要赢，显然 l e n len len要为奇数，还有石子可以选。

即： l e n < n len

然后情况2同理。

class Solution {
public:
    bool f1(int c[3],int n){
        if(!c[1]) return false;
        c[1]--;
        int x=min(c[1],c[2])*2+c[0]+1;
        if(c[1]>c[2]) x++;
        c[1]++;//这里要加回去,因为是传的引用,后面f2还要用c数组.
        return (x&1)&&(x& a) {
        int n=a.size();
        int c[3]={};
        for(int x:a) c[x%3]++;
        return f1(c,n)||f2(c,n);
    }
};