P8763 [蓝桥杯 2021 国 ABC] 异或变换

· · 题解

首先看到异或还有 t 的数据范围，立刻想到找规律，那么首先我们可以浅浅的造一个生成器。CODE：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,t,a[10010];
string s;
signed main()
{
    cin>>n>>t>>s;
    for(int i=1;i<=n;i++)a[i]=s[i-1]-'0';
    while(t--)
    {
        for(int i=n;i>1;i--)a[i]^=a[i-1];//倒着改可以避免异或时用了已修改的数的情况
        for(int i=1;i<=n;i++)cout<<a[i];
        cout<<'\n';
    }
    return 0;
}

我们可以代几组数据试一下。我先是测了：

5 10
11010

然后发现在第 8 行循环了，接着测：

5 40
11010

发现循环节相同，再测了几组 t 不等的情况，猜测 t 对循环节没有影响。

接着我们测 n，我从 5 开始测，测到 9 发现改变了，又跳着测了几组，发现 n=17 时循环节再次改变，我立刻想到循环节长度 l 可能为 \lceil\log_2 n\rceil，立刻执行，然后原神启动 AC。

代码十分的简短：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,t,a[10010];
string s;
signed main()
{
    cin>>n>>t>>s;
    for(int i=1;i<=n;i++)a[i]=s[i-1]-'0';
    int l=log2(n);
    if(pow(2,l)!=n)l++;
    l=pow(2,l);
    t%=l;//循环节长度为l，只用考虑取余后的部分
    while(t--)
    {
        for(int i=n;i>1;i--)a[i]^=a[i-1];
    }
    for(int i=1;i<=n;i++)cout<<a[i];
    return 0;
}