agc010 D Decrementing - 结论题

77 阅读 0 评论 51 点赞

我是靠谱客的博主怕黑哑铃，最近开发中收集的这篇文章主要介绍agc010 D Decrementing - 结论题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目大意：两人玩一个数列，每次每个人必须选择一个大于1的数字并让那个数字减去1，并且每个数字都除以减一后所有数字的gcd。不能操作者输，问谁赢。
题解：结论题，说了结论后就很好证了。
结论是，如果n是偶数，那么先手必胜（下文记做First）当且仅当数字之和是奇数。
否则，如果有奇数个偶数，则First。
否则，如果有多于1个奇数或唯一的一个奇数是1，则Second
否则，让那个唯一的奇数减一，所有数字除以gcd，回到最开始判断即可。
附上打表程序（哈你说为啥我说证明很显然但还有打表？

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<utility>
#define lint long long
#define gc getchar()
#define mp make_pair
#define fir first
#define sec second
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define clr(a,n) memset(a,0,sizeof(int)*((n)+1))
#define debug(x) cerr<<#x<<"="<<x
#define sp <<" "
#define ln <<endl
#include<assert.h>
using namespace std;
typedef pair<int,int> pii;
inline int inn()
{
    int x,ch;while((ch=gc)<'0'||ch>'9');
    x=ch^'0';while((ch=gc)>='0'&&ch<='9')
        x=(x<<1)+(x<<3)+(ch^'0');return x;
}
#define N 100000//1200000,when n=6 max=10
#define SIG 11
struct Trie{
    int node_cnt,rt,ch[N][SIG],val[N];
    Trie(){rt=node_cnt=1;}
    inline int insert(int *a,int n,int v,int x=1)
    {
        for(int i=1;i<=n;x=ch[x][a[i++]])
            if(!ch[x][a[i]]) ch[x][a[i]]=++node_cnt;
        return val[x]=v,0;
    }
    inline int count(int *a,int n,int x=1)
    {
        for(int i=1;i<=n;x=ch[x][a[i++]])
            if(!ch[x][a[i]]) return 0;
        return 1;
    }
    inline int getv(int *a,int n,int x=1)
    {   for(int i=1;i<=n;x=ch[x][a[i++]]);return val[x];    }
}t;
int a[100010];
int gcd(int a,int b) { return a?gcd(b%a,a):b; }
int dfs(int n)
{
    rep(i,1,n) assert(a[i]>0);
    int g=0;rep(i,1,n) g=gcd(g,a[i]);if(g>1) return 0;
    int can_win=0;if(t.count(a,n)) return t.getv(a,n);
    rep(i,1,n) if(a[i]>1)
    {
        a[i]--;int g=0;rep(j,1,n) g=gcd(g,a[j]);
        rep(j,1,n) a[j]/=g;
        can_win|=!dfs(n);
        rep(j,1,n) a[j]*=g;
        a[i]++;
        if(can_win) break;
    }
    rep(i,1,n) cerr<<a[i]<<" ";cerr<<": "<<can_win sp;lint s=0;rep(i,1,n) s+=a[i];s-=n;cerr<<s<<endl;
    if(n%2==0) assert((s&1ll)==can_win);
    else{
        int cnt=0;rep(i,1,n) if(a[i]%2==0) cnt++;
        if(cnt&1) assert(can_win);
        else{
            cnt=0;rep(i,1,n) cnt+=a[i]%2;
            if(cnt>1) assert(!can_win);
            else{
                int x=0;rep(i,1,n) if((a[i]>1)&&a[i]%2==1) x=i;
                if(x==0) assert(!can_win);
                else{
                    a[x]--;
                    int g=0;rep(i,1,n) g=gcd(g,a[i]);
                    rep(i,1,n) a[i]/=g;
                    assert(can_win==!dfs(n));
                    rep(i,1,n) a[i]*=g;
                    a[x]++;
                }
            }
        }
    }
    return t.insert(a,n,can_win),can_win;
}
int getans(int x,int n,int m) { if(x==n+1) return dfs(n);rep(i,1,m) a[x]=i,getans(x+1,n,m);return 0; }
int main()
{
//  int n,m;scanf("%d%d",&n,&m);getans(1,n,m);return debug(t.node_cnt)ln,0;
    int n=inn();rep(i,1,n) a[i]=inn();
    if(n%2==0) { int s=0;rep(i,1,n) s^=a[i];s&=1;return !printf(s?"Firstn":"Secondn"); }
//  int cnt=0;rep(i,1,n) if(a[i]%2==0) cnt++;if(cnt&1) return !printf("Firstn");
//  cnt=0;rep(i,1,n) cnt+=a[i]%2;if(cnt>1) return !printf("Secondn");
//  cnt=0;rep(i,1,n) if(a[i]%2==1&&a[i]>1) cnt++;if(!cnt) return !printf("Secondn");
    int fz=0;
    while(1)
    {
        int cnt=0;rep(i,1,n) if(a[i]%2==0) cnt++;if(cnt&1) return !printf(fz==0?"Firstn":"Secondn");
        cnt=0;rep(i,1,n) cnt+=a[i]%2;if(cnt>1) return !printf(fz==0?"Secondn":"Firstn");
        cnt=0;rep(i,1,n) if(a[i]%2==1&&a[i]>1) cnt++;if(!cnt) return !printf(fz==0?"Secondn":"Firstn");
        int x=0,g=0;rep(i,1,n) if(a[i]%2==1&&a[i]>1) x=i;a[x]--;rep(i,1,n) g=gcd(g,a[i]);
        rep(i,1,n) a[i]/=g;fz^=1;//rep(i,1,n) debug(a[i])sp;cerr ln;
    }
    return 0;
}