agc010 D Decrementing - 结论题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#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;
}