题解 P4405 【[ZJOI2009]硬币游戏】

· · 题解

把正面当作0，反面当作1

注意到每一次变换之后所得到的结果取决于变换之前该位置左右两个硬币的异或值

下面让我们找一下规律，设第2i-1个位置刚输入时候时的状态是Ai，空位置就用0代替 有一点点省略，相信大家还是看得懂的

这样下来，我们大概能够发现，经过2^k次变换之后，A[i]会变成A[i+2^(k-1)]^[i-2^(k-1)]【暂时不考虑k=1的情况】

于是对T按位处理，如果T从小到大第k位为1，那么就把原数组的每一个A[i]进行一次替换

最后如果T为奇数，就再进行一次变换

代码如下，注意记得要提前处理出每一个2^k 还有就是为了取模时候方便，我的数组是从0开始使用的

#include <stdio.h>
#include <algorithm>
using namespace std;
typedef long long llw;
int c[4][200010];
llw n2[66];
llw T;
int n;

int main()
{
    int k=0;
    n2[0]=1;
    for(int i=1;i<=60;i++) n2[i]=n2[i-1]<<1;//预处理2^i
    scanf("%d %lld",&n,&T);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&c[0][i<<1]);
        c[0][i<<1]--;//注意原来输入时候输入的是1和2，而不是用于异或运算的0和1
    }
    for(llw i=1;n2[i]<=T;i++)
    {
        if(n2[i]&T)//判断第i位是否为1
        {
            k^=1;
            for(int j=0;j<n;j++)
            {
                c[k][j<<1]=c[k^1][(((j-n2[i-1])%n+n)%n)<<1]^c[k^1][((j+n2[i-1])%n)<<1];//注意要*2
            }
        }
    }
    if(T&1)//判断是否为奇数
    {
        k^=1;
        for(int i=0;i<n;i++) c[k][(i<<1)+1]=c[k^1][i<<1]^c[k^1][((i<<1)+2)%(n<<1)];
        for(int i=1;i<(n<<1);i+=2) printf("0 %d ",c[k][i]+1);
    }
    else
    {
        for(int i=0;i<(n<<1);i+=2) printf("%d 0 ",c[k][i]+1);
    }
    return 0;
}