自动搬运

查看原文

来自洛谷，原作者为

	ryf_loser qq 号 3622570940//飞雪连天射白鹿 笑书神侠倚碧鸳//AC 1k [CSP-S 2024] 超速检测 祭

搬运于2025-08-24 22:42:13，当前版本为作者最后更新于2022-12-23 21:10:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

2024.3.11 添加第二组演示样例。

2024.3.12 修改第一组演示样例，添加一点点证明。

暴力显然寄飞了，考虑优化，这种情况往往是有规律的，我举两个例子样例进行模拟的。

输入 $n=4,t=5$，不难发现，从第 4 次就开始循环了。

$0. 0110 \leftarrow$

$1. 0101$

$2. 0111$

$3. 0100$

$4. 0110 \leftarrow$

用样例再来搞一下，输入 $n=5,t=9$

$0. 10110$

$1. 11101 \leftarrow$

$2. 10011$

$3. 11010$

$4. 10111$

$5. 11100$

$6. 10010$

$7. 11011$

$8. 10110$

$9. 11101 \leftarrow$

有感觉了么？

那么，最终的规律是当大于等于 $n$ 的一个 2 的整数次幂情况下，必定存在循环。

可以证明，令 $x=2^k$，根据题目。

$s_{x,j}=s_{x-1,j}\oplus s_{x-1,j-1}$

$s_{x-1,j}=s_{x-2,j}\oplus s_{x-2,j-1}$

$s_{x-1,j-1}=s_{x-2,j-1}\oplus s_{x-2,j-2}$

……

由此递推下去，可得。

$s_{x,j}=s_{\frac{x}{2},j}\oplus s_{\frac{x}{2},j-x}$

根据异或性质可以发现，第 $x$ 的序列是由两次 $\frac{x}{2}$ 的序列得来的。

当 $x \geq n$ 时，这种重复操作变得没有意义，准确来说，当 $x \leq n$ 时必定存在与此时字符串 $s$ 完全相同。

时间复杂度为 $O(n \log \min(n,t))$ 级别。秒了。

AC CODE

#include<stdio.h>
long long n,t;
int x=1;
char s[10005];
int main(){
	scanf ("%lld%lld",&n,&t);
	scanf ("%s",s);
	while(x<n)x<<=1;t=t%x;
	for(int i=0;i<t;i++)
		for(int j=n-1;j>=1;j--)
			s[j]=(s[j]-'0')^(s[j-1]-'0')+'0';
	printf ("%s",s);
	return 0;
}