筱玛爱游戏——线性基
链接:https://ac.nowcoder.com/acm/contest/946/E
来源:牛客网-----------------------------------------------------------------------------------------------
题解:
一.首先得先学“线性基”。
不知道的可以不用往下看了。
这里只说下要用到的关于“线性基”的性质:线性基集合中的任何子集的异或和都不会为0
二.如果 插入的这个数的二进制 第i位 为 1,而 线性基集合 的二进制位数刚好没有 第 i 位,
则说明该数可以选,并且不会使得线性基集合子集
异或和 位 0 的情况出现。我们就可以统计一下有多少个数可以选的,然后根据可选个数判断奇偶性就可以知道是先手还是后手赢了。
//#pragma comment(linker, "/STACK:1024000000,1024000000") //#pragma GCC optimize(2) //#include <bits/stdc++.h> #include <algorithm> #include <iostream> #include<sstream> #include<iterator> #include<cstring> #include<string> #include<cstdio> #include<cctype> #include<vector> #include<deque> #include<queue> #include<stack> #include<map> #include<list> #include<set> using namespace std; typedef double dou; typedef long long ll; typedef pair<int, int> pii; #define pai acos(-1.0) #define M 200005 #define inf 1e18 #define mod 1000000007 #define left k<<1 #define right k<<1|1 #define W(a) while(a) #define ms(a,b) memset(a,b,sizeof(a)) ll num[M]; ll ans, n, m, t; int insert(ll x) { for (int i = 61; i >= 0; i--) { if (x >> i & 1) { if (!num[i])//如果线性基二进制中没有这一位,那就是可以选这个数 { num[i] = x; return 1;//可选数+1 } x ^= num[i]; } } return 0;//如果这个数的每一位都和线性基二进制重合,那么就是不可以选的 } int main() { ios::sync_with_stdio(false); cin >> n; for (int i = 1; i <= n; i++) { cin >> t; ans+=insert(t);//插入线性基 } if (ans&1) cout << "First" << endl; else cout << "Second" << endl; return 0; }