【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;
}

【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;
}

【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;
} 

【POJ 2234】Matches Game

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

卧槽,真™有板题QAQ
证明可以看这里:https://maxmute.com/

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

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;
}

int main(){
	int n; while (~scanf("%d",&n)) {
		int vout = read();
		for (int i=1;i<n;i++) vout ^= read(); 
		if (!vout) cout<<"No"<<endl;
		else cout<<"Yes"<<endl;
	}
	return 0;
} 

【Vijos 1196】吃糖果游戏

题目传送门:https://vijos.org/p/1196

卧槽,这个和1655不一毛一样吗?

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

const int MAXN = 100000;

char s1[MAXN],s2[MAXN];
int l1,l2;

inline bool leg(int c){
	return c == 2 || c == 3 || c == 7 || c == 8;
}

int main(){
	while (scanf("%s%s",s1+1,s2+1) == 2){
		l1 = strlen(s1+1); 
		l2 = strlen(s2+1);
		if (leg(s1[l1]-'0') && leg(s2[l2]-'0')) cout<<"Shadow"<<endl;
		else cout<<"Matrix67"<<endl;
	}
	return 0;
}

【Vijos 1655】萌萌的糖果博弈

题目传送门:https://vijos.org/p/1655

这个题嘛,暴力打印一下40以内的情况如下:
78973673526
不难发现,个位为2,3,7,8的话,则为先手必败
于是乎,读入+输出即可

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

const int MAXN = 100000;

char s1[MAXN],s2[MAXN];
int l1,l2;

inline bool leg(int c){
	return c == 2 || c == 3 || c == 7 || c == 8;
}

int main(){
	while (scanf("%s%s",s1+1,s2+1) == 2){
		l1 = strlen(s1+1); 
		l2 = strlen(s2+1);
		if (leg(s1[l1]-'0') && leg(s2[l2]-'0')) cout<<"SheepDaddy"<<endl;
		else cout<<"MengMeng"<<endl;
	}
	return 0;
}