题解：AT_agc010_d [AGC010D] Decrementing

_Seren_ · 2026-08-07 15:45:27 · 题解

模拟赛原题。我去为啥题解都观察到了偶数个数奇偶性状物，那我在干嘛？？不至于假掉了吧。不管先写篇题解接受大众审判下。

首先容易发现数列含 1 时只能一步步减，记 sum=\sum_{i=1}^{n}a_i，经过 sum-n 次操作得到全 1 序列，所以 sum-n 为奇数时为必胜态，偶数则为必败态。

考虑不含 1 的情况。sum-n 为偶会被认为是“败态”，但真的吗？一次操作 sum \leftarrow sum-1 后 sum-n 为奇数。如果可以再通过 sum \leftarrow sum \div g 使得 sum-n 为偶数就翻盘了。

记 sum = g \times k + 1，则操作相当于 sum \leftarrow k，要想翻盘需要 (g-1) \times k 为奇，即 g 为偶数，k 为奇数。……等等，“翻”前后 sum 都是奇数，说明还可能被对面翻回来？？

考虑“翻”的过程中序列发生了什么：【n-1 个偶和 1 个奇】 -> n 个偶 -> 一定有奇，可能有偶。

那对面【想翻回来】肯定得把奇数全减成偶数，那你跟着破坏呗，把他减成的偶数再减成奇数。那 1 呢？对面根本没法减，没有影响对吧。不过如果你刚翻完就刚好留给对方一个【n-1 个偶和 1 个奇】就没法阻止了。

好的差不多了，刚才我们一直说的是翻盘者的视角，现在回到题目。开局先判 sum-n 奇偶性。

• 如果奇数就是“胜态”，但要注意对方能不能翻：

  • 如果全是偶数，你不得不减一，留给对面一个【n-1 个偶和 1 个奇】，被翻了 \ll。
  • 否则一定丢给对面一个【想翻回来】的状态，而你可以维持数列中有至少两个奇数，所以一定能通过刚才介绍的方法阻止对面的翻盘，直接判胜。

  什么你说你阻止翻的过程中会触发 \div g？但由于不全是偶数，\div g 是不影响奇偶性的。

• 如果是偶数就是“败态”，考虑翻盘：

  • 如果是【n-1 个偶和 1 个奇】直接翻。
  • 否则全程无法翻盘（应该容易理解），直接判负。

  什么你说万一能翻但会被对方翻回来能不能等会再翻？不可以，简单模拟下样例就会发现错失机会后局面就失控了，对方很容易维持至少两个奇数，你无法达到【n-1 个偶和 1 个奇】状态。

分析下时间复杂度。

由于 a 一直在减少，\gcd 不断除以正整数，模拟双方操作是 \log 级的，具体可以参考代码。a_i \leftarrow a_i \div g 可以直接 O(n) 跑。总复杂度 O(n\log n)。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int T,n,a[N];
int dfs(int now){
    long long sum=0;int cnt=0,pos=0;
    for(int i=1;i<=n;i++){
        sum+=a[i];
        if(a[i]%2==1)cnt++,pos=i;
    }
    bool flg=0;
    for(int i=1;i<=n;i++)
        if(a[i]==1){flg=1;break;}
    if(flg){
        if((sum-n)%2==1)return now;
        return 3-now;
    }

    if((sum-n)&1){
        if(cnt>0)return now;
        else {a[1]--;return dfs(3-now);}
    }
    if(cnt==1){
        a[pos]--;
        int g=a[1];
        for(int i=2;i<=n;i++)
            g=__gcd(g,a[i]);
        for(int i=1;i<=n;i++)a[i]/=g;
        return dfs(3-now);
    }else return 3-now;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    if(n==1){
        if(a[1]==1)printf("Second\n");
        else printf("First\n");
        return 0;
    }
    if(dfs(1)==1)printf("First\n");
    else printf("Second\n");
    return 0;
}