【BZOJ 4589】Hard Nim

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4589

解题报告

我们考虑用SG函数来暴力DP
显然可以用FWT来优化多项式快速幂
总的时间复杂度:$O(n \log n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009; 
const int MOD = 1000000007;
const int REV = 500000004;

bool vis[N];
int arr[N];

inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

inline int Pow(int w, int t) {
	int ret = 1;
	for (; t; t >>= 1, w = (LL)w * w % MOD) {
		if (t & 1) {
			ret = (LL)ret * w % MOD;
		}
	}
	return ret;
}

inline void FWT(int *a, int len, int opt = 1) {
	for (int d = 1; d < len; d <<= 1) {
		for (int i = 0; i < len; i += d << 1) {
			for (int j = 0; j < d; j++) {
				int t1 = a[i + j], t2 = a[i + j + d];
				if (opt == 1) {
					a[i + j] = (t1 + t2) % MOD;
					a[i + j + d] = (t1 - t2) % MOD;
				} else {
					a[i + j] = (LL)(t1 + t2) * REV % MOD;
					a[i + j + d] = (LL)(t1 - t2) * REV % MOD;
				}
			}
		}
	}
}

int main() {
	for (int n, m; ~scanf("%d %d", &n, &m); ) {
		memset(arr, 0, sizeof(arr));
		for (int i = 2; i <= m; i++) {
			if (!vis[i]) {
				arr[i] = 1;
				for (int j = i << 1; 0 <= j && j <= m; j += i) {
					vis[j] = 1;
				}
			}
		}
		int len = 1; 
		for (; len <= m; len <<= 1);
		FWT(arr, len);
		for (int i = 0; i < len; i++) {
			arr[i] = Pow(arr[i], n);
		}
		FWT(arr, len, -1);
		printf("%d\n", (arr[0] + MOD) % MOD);
	}
	return 0;
}

【Codeforces 812E】Sagheer and Apple Tree

相关链接

题目传送门:http://codeforces.com/contest/812/problem/E
官方题解:http://codeforces.com/blog/entry/52318

解题报告

我们发现,如果操作同叶子结点的深度奇偶性不同的结点
那么对手总可以操作刚刚你操作的那些苹果

所以结果只与深度同叶子结点奇偶性相同的点有关
更进一步观察发现,实质上就是这些点组成的$NIM$游戏
于是乘一乘、加一加就好了

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int M = 10000009;

int n, prt, tot, dep[N], v[N], in[N];
int head[N], nxt[N], to[N], cnt[M];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void AddEdge(int u, int v) {
	static int E = 1; in[v]++; in[u]++;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
}

void DFS(int w) {
	for (int i = head[w]; i; i = nxt[i]) {
		dep[to[i]] = dep[w] + 1;
		DFS(to[i]);
	}
}

int main() {
#ifdef DBG
	freopen("11input.in", "r", stdin);
#endif
	n = read();
	for (int i = 1; i <= n; i++) {
		v[i] = read();
	}
	for (int i = 2; i <= n; i++) {
		AddEdge(read(), i);
	}
	DFS(1);
	for (int i = 2; i <= n; ++i) {
		if (in[i] == 1) {
			prt = (dep[i] & 1);
			break;
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if ((dep[i] & 1) == prt) {
			ans ^= v[i];
		}
	}
	LL vout = 0;
	tot = n;
	for (int i = 1; i <= n; i++) {
		if ((dep[i] & 1) == prt) {
			cnt[v[i]]++;
			--tot;
		}
	}
	for (int i = 1; i <= n; i++) {
		if ((dep[i] & 1) != prt) {
			int tt = ans ^ v[i];
			if (tt < M) {
				vout += cnt[tt];
			}
		}
	}
	if (!ans) {
		vout += tot * (tot - 1ll) / 2;
		vout += (n - tot) * (n - tot - 1ll) / 2;
	}
	cout<<vout<<endl;
	return 0;
}

【POJ 3922】A simple stone game

相关链接

题目传送门:http://poj.org/problem?id=3922
神犇题解:http://www.cnblogs.com/jianglangcaijin/archive/2012/12/19/2825539.html

解题报告

根据$k = 1$的情况,我们发现在二进制下,我们取走最低位的$1$,对手取不走较高位的$1$
所以如果不是二的整次幂,那么先手必胜

再来看看$k = 2$的情况
根据$HINT$我们把每个整数拆成若干个不同、不相邻的斐波那契数之和,表示成二进制状态
之后跟据$k = 1$时的推论,我们取走最低位的$1$,对手不能直接取走较高位的$1$

先在我们看我们依赖拆分数列的哪些性质:

存在一种拆分使得选中的项的任意相邻两项超过$k$倍

于是我们尝试构造拆分数列$a_i$
我们设$b_i$为$a_1 \to a_i$能拼出的极长的前缀长度
不难发现$a_i = b_{i-1}+1, b_i=a_i+b_j$,其中$j$尽可能大,且$a_j k < a_i$

于是这题就做完啦
似乎这个问题还是博弈论里的一个经典问题,叫”$k$倍动态减法问题”
似乎某年国家集训队论文里还提出了另外的算法,对于某些数据会更优

Code

#include<cstdio>
#include<iostream>
#define LL long long
using namespace std;

const int N = 10000000;

int n,k,x,y,a[N],b[N]; 

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	for (int t = 1, T = read(); t <= T; ++t) {
		n = read(); k = read();
		a[0] = b[0] = x = y = 0;
		while (a[x] < n) {
			a[x + 1] = b[x] + 1;
			for (++x; (LL)a[y + 1] * k < a[x]; ++y);
			b[x] = y? b[y] + a[x]: a[x];
		}
		if (a[x] == n) {
			printf("Case %d: lose\n", t);
		} else {
			int ans = 0;
			for (; n && x; --x) {
				if (n >= a[x]) {
					n -= a[x];
					ans = a[x];
				}
			}
			printf("Case %d: %d\n", t, ans);
		}
	}
	return 0;
}

【BZOJ 2437】[NOI2011] 兔兔与蛋蛋

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2437
神犇题解:http://blog.csdn.net/qpswwww/article/details/45368587

解题报告

我们先将整个棋盘黑白染色,将空格棋子所在方格的颜色分类
在可相互转化的状态之间连边,那么这就是一张二分图了

那么原题的问题转换为:

给定一张二分图,每次沿边移动一次
每个点只能到达一次,最后谁不能动谁就输了
询问每一个点作为起点时是否先手必胜

考虑一个点如果在任意一种最大匹配当中,那么先手每一次走匹配边,则后手必败
换一句话来说,如果一个点一定在最大匹配当中,那么这个点是先手必胜的
再考虑一下,如果一个点不一定在最大匹配当中,那么删掉这个点之后存在最大匹配,那后手走到那个点去就可以了!
再换一句话来说,如果一个点不一定在最大匹配中,那么这个点先手必败

现在我们只需要求出一个点是否在最大匹配中就可以了!
我们可以枚举这个点,将其删掉后跑最大匹配验证,但复杂度是$O(n^4)$的
或者我们可以用今年冬令营的那个一般图匹配的算法来做,时间复杂度是$O(n^3)$的

不过我们可以又一个常数更小的算法

我们可以先求出一个最大匹配,然后假设当点在点$a$
将其删掉后,看$a$的匹配点$b$还能不能匹配即可

吐槽

博弈题居然还能这么玩!
真的是长见识了 _(:з」∠)_
不过代码好难写啊,不想写代码 ┑( ̄Д  ̄)┍

【BZOJ 3576】[HNOI2014] 江南乐

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3576
神犇题解Ⅰ:http://blog.csdn.net/regina8023/article/details/45034045
神犇题解Ⅱ:http://blog.csdn.net/gromah/article/details/27326991

解题报告

这么麻烦的游戏过程,不是找规律就是SG函数来做咯!
然后手玩一下样例,发现这货并没有什么性质的样子

于是考虑SG函数:
因为每一堆石子相互独立,由SG定理可得:
一个石子堆的SG函数等于分开后各堆石子的SG函数的NIM和
于是考虑暴力枚举M。
这样的话,我们就可以在 $ O({n^2})$ 的时间复杂度内解决该问题了

更进一步,我们发现在枚举M的过程中
因为亦或同一个数偶数次相当于没有亦或
所以我们不必枚举所有的M,只需要分奇偶讨论一下就可以了
于是就用莫比乌斯反演经常用到的“下底函数分块”来解决这个问题啦!
时间复杂度:$ O(n\sqrt n )$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100000+9;

int F,T,n,vis[N],sg[N];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline int Get_Sg(int w) {
	if (w < F) return sg[w] = 0;
	else if (~sg[w]) return sg[w];
	else if (sg[w] = 0, 1) {
		for (int l=2,r,a,b;l<=w;l=r+1) {
			r = w / (w / l);
			for (int i=l;i<=min(w,l+1);i++)	{
				Get_Sg(w / i + 1);
				Get_Sg(w / i);
			}
		}
		for (int l=2,r,a,b,tmp;l<=w;l=r+1) {
			r = w / (w / l); 
			for (int i=l,tmp=0;i<=min(w,l+1);i++,tmp=0)	{
				if ((w % i) & 1) tmp ^= sg[w / i + 1];
				if ((i - (w % i)) & 1) tmp ^= sg[w / i];
				vis[tmp] = w;
			}
		}
		for (int i=0;;i++)
			if (vis[i] != w)
				return sg[w] = i;
	}
}

int main(){
	memset(sg,-1,sizeof(sg));
	T = read(); F = read();
	for (int t=T,vout;t;--t) {
		n = read(); vout = 0;
		for (int i=1;i<=n;i++) 
			vout ^= Get_Sg(read());
		if (t<=1) printf("%d\n",!vout?0:1);
        else printf("%d ",!vout?0:1);
	}
	return 0;
}

【算法笔记】Bouton定理

概述

对于NIM游戏,相信大家都知道一个结论:

每一堆石子的数量给异或起来,若为0则先手必败,否则先手必胜

这个结论就是Bouton定理。
但对于这个定理,我一直没有找到简洁的证明
今日再一次翻看《白书》,终于觅得,于是记录于此

Bouton定理的结论

对于原版的NIM游戏
若每队石子的个数的NIM和为0,则先手必败
否则,先手必胜

Bouton定理的证明

参见《算法竞赛·入门经典·训练指南》P135

后记

为什么感觉这么鬼畜…..
最关键的证明部分是一个引用QAQ
唉,懒癌晚期,放弃治疗…..
jslugcg9lhkh0ix9zh

【Codeforces 662A】Gambling Nim

题目传送门:http://codeforces.com/problemset/problem/662/A
官方题解:http://codeforces.com/blog/entry/44408

说人话就是亦或和为0的概率是多少
考虑把ai全部亦或起来为sum的话
那就是求{ai^bi}有多少个子集亦或和为sum
这样的话,岂不就是线性基的拿手好戏了?

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 500000+9;
const int SGZ = 61+9;

int n,cnt;
LL a[N],b[N],bas[SGZ],sum; 

inline LL read(){
	char c=getchar(); LL ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline bool insert(LL w) {
	for (int i=61;~i;i--) if (w&(1LL<<i)) {
		if (bas[i]) {
			w ^= bas[i];
		} else {
			bas[i] = w;
			return true;
		}
	}	
	return false;
}

inline LL pow(LL w, int t) {
	LL ret = 1;
	while (t) {
		if (t & 1) ret *= w;
		w *= w; t >>= 1;
	}
	return ret;
}

int main(){
	n = read();
	for (int i=1;i<=n;i++) {
		a[i] = read();
		b[i] = read();
		sum ^= a[i];
		cnt += insert(a[i] ^ b[i]);
	}
	if (!cnt && !sum) {
		puts("0/1");
	} else if (insert(sum)) {
		puts("1/1");
	} else {
		printf("%I64d/%I64d\n",pow(2LL,cnt)-1,pow(2LL,cnt));
	}
	return 0;
}

【BZOJ 3105】[cqoi2013] 新Nim游戏

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3105

这个题目,考虑两个回合之后。
假如对手能够在在第二个回合搞出一个Nim和为0的东西,那我们岂不是输了?
所以我们不能给对手搞出Nim和为0的机会,而Nim和为Xor,不存在子集Nim和为0是线性无关
而我们又要子集最大(损失最小),所以我们要求的是一个极大线性无关子集
然后我们发现,这货不是线性基吗?
于是水之

#include<bits/stdc++.h>
#define LL long long
using namespace std;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int bas[32],arr[109];
inline bool update(int w) {
	for (int i=0;i<=31;i++) if (w & 1<<i) 
		if (bas[i]) w ^= bas[i];
		else {bas[i] = w; return 1;}
	return 0;
}

int main(){
	int k = read(); LL vout = 0; 
	for (int i=1;i<=k;i++) arr[i] = read(), vout += arr[i];
	sort(arr+1,arr+1+k);
	for (int i=k;i;i--) vout -= update(arr[i])*arr[i];
	printf("%lld\n",vout);
	return 0;
}

【算法笔记】博弈论

这货,做了一点题,看了一点论文,觉得有以下几个要点:
1)先猜结论,之后再想办法证明
2)不要试图手玩,玩不出来的
3)SG值相同的子游戏,对于游戏和来说可以相互替换
4)以上都不行的时候,就先找一种比较宽泛的必胜/必败状态,再试图推广

另外,还学到了一点绍一的黑科技,现在先暂时不研究,特意截图以供以后研究:
sg_min_one

【POJ 2425】A Chess Game

题目传送门:http://poj.org/problem?id=2425

这个题目,第一眼想到肯定是状压SG,然后发现MLE+TLE
于是发现棋子之间互不影响,于是等价为NIM
证明不会QAQ,不过贾志豪的论文里讲:这是性质QAQ

MD之前看的中文体面有问题,浪费了两个小时
以后还是乖乖看原题面吧!

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 1000+9;

int n,head[MAXN],T,nxt[MAXN*MAXN],to[MAXN*MAXN],m,f[MAXN],vout,dig[MAXN],tot;

inline int read(){
	char c=getchar(); int ret=0;
	while (c<'0'||c>'9') c=getchar();
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret;
}

inline void AddEdge(int u, int v){
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
}

int Get(int w){
	if (!~f[w]) { 
		int tmp = ++tot;
		for (int i=head[w];i;i=nxt[i]) Get(to[i]);
		for (int i=head[w];i;i=nxt[i]) dig[f[to[i]]] = tmp;
		for (int i=0;i<MAXN;i++) if (dig[i] != tmp) {f[w] = i; break;}
	} return f[w];
}

int main(){
	while (~scanf("%d",&n)) {
		T = 0; memset(head,0,sizeof(head)); memset(f,-1,sizeof(f));
		for (int i=1,tmp;i<=n;i++) {
			tmp = read(); 
			if (!tmp) f[i] = 0;
			else for (int j=tmp;j;j--) AddEdge(i,read()+1);
		}
		while (m = read()) { vout = 0;
			for (int i=1;i<=m;i++) vout ^= Get(read()+1); 
			if (!vout) printf("LOSE\n");
			else printf("WIN\n");
		} 
	}
	return 0;
}