「ZJOI2009」硬币游戏

一道贼难的递推

_{据说还是浙江省选}

题目大意是这样：

在桌子的边缘上划分出 $2n$ 个位置并按顺时针把它们标号为 $1,2,\ldots,2n$，然后把 $n$ 个硬币放在标号为奇数的位置上。接下来每次按如下操作：在任意两个硬币之间放上一个硬币，然后将原来的硬币拿走；所放硬币的正反面由它两边的两个硬币决定，若两个硬币均为正面朝上或反面朝上，则所放硬币为正面朝上，否则为反面朝上。

然后问你操作 $T$ 次后桌子边缘上硬币的情况

首先很容易发现，设正面朝上为 $1$，反面朝上为 $0$，则每进行一次操作，其实就是将两个硬币的值异或后放在中间，再将两个硬币去掉，重复 $T$ 次。

_{然后开始枚举找规律}

发现经过 $2$ 次变换后，$a[i]=a[i-2]\ \text{xor}\ a[i+2]$，即两次操作后这枚硬币的值变为了它左边第 $2$ 枚硬币与右边第 $2$ 枚硬币异或的值。

然后继续延伸，可得到这样一个结论：

$$a[i]=a[i-2 ^{i-1}]\ \text{xor}\ a[i+2 ^{i-1}]$$

即第i枚硬币的值为它左边第 $2 ^{i-1}$ 枚硬币与它右边第 $2 ^{i-1}$ 枚硬币的异或值。

然后就很简单了，把 $T$ 二进制拆分，若第 $k$ 位为 $1$，就用刚才的结论操作一次，操作一次时间复杂度为 $O(n)$，大大节省时间复杂度。

需要注意的是 $2 ^0$，即 $1$ 的情况，若 $T$ 是一个奇数，就要再进行一次操作，处理 $0$ 的位置。

最后输出就可以了，总时间复杂度为 $O(n\log T)$。

code:

#include<stdio.h>
int n,k;
long long t;
int ans[201010],a[2][101010];
int main()
{
	scanf("%d%lld",&n,&t);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[0][i]);
		a[0][i]--;
	}
	for(int j=1;(1ll<<j)<=t;j++)
	{
		if(t&(1ll<<j))
		{
			long long p=(1ll<<j);
			for(int i=1;i<=n;i++)
			{
				long long x=(i-(p>>1)%n+n-1)%n+1;
				long long y=(i+(p>>1)%n+n-1)%n+1;
				a[k^1][i]=a[k][x]^a[k][y];
			}
			k^=1;
		}
	}
	for(int i=1;i<=n;i++)
		ans[2*i-1]=a[k][i];
	if(t&1)
	{
		for(int i=1;i<=n;i++)
			ans[2*i]=ans[2*i-1]^ans[i==n?1:(2*i+1)];
		for(int i=1;i<=n;i++)
			ans[2*i-1]=-1;
	}
	else
		for(int i=1;i<=n;i++)
			ans[2*i]=-1;
	for(int i=1;i<=2*n;i++)
		printf("%d ",ans[i]+1);
	return 0;
}