P8763

· · 题解

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;
}