蓝桥杯 异或变换

小蓝有一个 01 串 s = s1 s2 s3 · · · sn。
以后每个时刻，小蓝要对这个 01 串进行一次变换。每次变换的规则相同。
对于 01 串 s = s1 s2 s3 · · · sn，变换后的 01 串 s′ = s′1 s′2 s′3· · · s′n 为：
s′1 = s1; 
s′i = si-1 ⊕ si。
其中 a ⊕ b 表示两个二进制的异或，当 a 和 b 相同时结果为 0，当 a 和 b不同时结果为 1。
请问，经过 t 次变换后的 01 串是什么？

 解题思路：

暴力做法：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e3+10;
ll n,t;
bool dp[maxn];
bool temp[maxn];
int main()
{
	scanf("%lld %lld",&n,&t);
	getchar();
	string str;cin>>str;
	for(int i=0;i<str.size();i++)
	{
		if(str[i]=='0')dp[i]=0;
		else dp[i]=1;
	}
	temp[0]=dp[0];
	while(t--)
	{
		for(int i=1;i<str.size();i++)
		{
			temp[i]=dp[i]^dp[i-1];
		}
		for(int i=0;i<str.size();i++)
		{
			dp[i]=temp[i];
		}
	}
	for(int i=0;i<str.size();i++)
	{
		printf("%d",dp[i]);
	}
	printf("\n");
	return 0;
}

 这样的话只能过部分数据

 尝试优化：

对于一个01串他的变换次数是有一个周期的。这个周期是大于等于长度的最小的2的幂次。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e4+10;
ll n,t;
bool dp[maxn];
bool temp[maxn];
int main()
{
	scanf("%lld %lld",&n,&t);
	getchar();
	string str;cin>>str;
	for(int i=0;i<str.size();i++)
	{
		if(str[i]=='0')dp[i]=0;
		else dp[i]=1;
	}
	temp[0]=dp[0];
	long long  len=1;
	while(len<n)
	{
		
		len=len<<1;
		//mod++;
	}
	t%=len;
	while(t--)
	{
		for(int i=1;i<str.size();i++)
		{
			temp[i]=dp[i]^dp[i-1];
		}
		for(int i=0;i<str.size();i++)
		{
			dp[i]=temp[i];
		}
	}
	for(int i=0;i<str.size();i++)
	{
		printf("%d",dp[i]);
	}
	printf("\n");
	return 0;
}