进化（D.cpp 1S 512M）

传送门

题解

首先，$b[i]=(a[i+1]+a[i-1])\bmod 2$ 等价于 $b[i]=a[i+1] \oplus a[i-1]$。

我们考虑一种暴力做法。

假设进化 $m$ 次后的数组为 $a_m$，那么注意到 $a_m[i]$ 可以转移到 $a_{m+1}[i+1]$ 和 $a_{m+1}[i-1]$。

抽象一下，会发现对于每个 $i$，$a_1[i]$ 有 $2^T$ 种路径转移到 $a_T$。

我们可以把每一条路径用一个二进制数（bitset？）概括一下（$0$ 表示向左，$1$ 表示向右），枚举路径判断每个 $a_1[i]$ 对 $a_T$ 的影响。

复杂度 $O(n 2^T)$，~~连最小的部分分都过不了。~~

但是这个做法有巨大的优化空间，首先容易发现，并不需要枚举每条路径，因为每条路径的终点与且仅与路径中 $0$/$1$ 的个数有关，我们利用组合数可以把复杂度压至 $O(n^2)$（假如有某种方法可以预处理极其巨大的组合数）。

但这还远不是这条思路的极限，假设每个 $i$ 到 $j$ 的路径中有 $r$ 个 $1$，显然有 $T-r$ 个 $0$。

那么可以得到 $j-i=r-(T-r)=2r-T$。

注意到，$i$ 对 $j$ 的影响只与 $a_1[i]$ 和 $\dbinom{T}{r}$ 的奇偶性有关，概括成数学语言 $i$ 对 $j$ 的影响就是 $\dbinom{T}{r}\bmod 2 \cdot a_1[i]$（这个 $r$ 是可以求出来的但我们暂且放一放）。

看到组合数模一个小质数的形式想到 lucas 定理，即：

$$\dbinom{T}{r}\bmod 2=\dbinom{\left\lfloor T/2 \right\rfloor}{\left\lfloor r/2 \right\rfloor}\cdot \dbinom{T \bmod 2}{r\bmod 2}\bmod 2$$

左边还可以再拆但是我不想写了，我们换一种写法，将 $T$ 在二进制下的第 $c$ 位记作 $T_{c}$（其实并不存在这样的记法只是我为了方便叙述乱搞的），$r$ 同理。

$$\dbinom{T}{r}\bmod 2 = \dbinom{T_{1}}{r_{1}}\cdot\dbinom{T_{2}}{r_{2}}\cdots \dbinom{T_{\log_T}}{r_{\log T}}$$

注意到 $\dbinom{T_{c}}{r_{c}}$ 其实只有 $\dbinom{0}{0}=1,\dbinom{1}{1}=1,\dbinom{0}{1}=0,\dbinom{1}{0}=1$ 四种可能。发现当 $(T)_c=0$ 时结果与且仅与 $(r)_c$ 有关，想到将原先 $T$ 的每一位拆出来分别计算，下次计算时就由这次的结果为基础，以构造成 $10\dots00$ 的形式（通过部分分也可以想到这一点），设每次拆出来的数为 $t$。

所以 $\dbinom{t}{r}\bmod 2 = 1$ 当且仅当 $\forall (t)_c=0,(r)_c=0$。

换句话说，只有当 $r$ 的二进制为 $10\dots00$ 或者 $00\dots00$ 时，$\dbinom{t}{r}\bmod 2=1$。

进一步，$\dbinom{t}{r}\bmod 2=1$ 当且仅当 $r=0$ 或 $r=t$。

由于 $j-i=2r-t$，故 $a_t[j]$ 只会被 $a_1[j-t]$ 和 $a_1[j+t]$ 影响。概括成数学语言就是 $a_t[j]=a_1[j-t]\oplus a_1[j+t]$。

但是这里有个问题，数组会越界。

容易想到把它转化成一个等价的环形问题（~~其实并不容易~~）。

考虑构造一个环 $c$，它长这样：

在环 $c$ 中进行题目描述中的“进化”操作和 $a$ 是等价的。

首先，每个 $a[2]$ 到 $a[n-1]$ 中显然是等价的。

$a[1]$ 和 $a[n]$ 的另一边为 $0$ 显然也是等价的。

对于两端的 $0$，它的两侧永远都是相等的，无论何时都是 $0$。

（~~我也不知道是怎么想出来的，反正也不是我想出来的。~~）

用数组存的时候左边那个 $0$ 下标设为 $0$ 然后顺时针转就行了。

综上，最终做法如下：

取出 $T$ 二进制最低位（记为 $t$），将 $T$ 减去 $t$。
通过现有数组 $a$ 构造出环 $c$。
对于所有 $1\le i \le n$，计算出 $b[i]=c[(i+t)\bmod (n\times 2+2) ] \oplus c[(i-t)\bmod (n\times 2+2) ] $（注意取模考虑负数）。
将整个 $b$ 赋给 $a$。
重复以上操作直至 $T$ 归零。

最终的数组 $a$ 即为答案。

每一层复杂度 $O(n)$，最多有 $\log T$ 层，时间复杂度 $O(n\log T)$，空间复杂度 $O(n)$，可以通过此题。

code

#include<iostream>
#include<algorithm>
#include<string.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#include<vector>
#define pbk(a) emplace_back(a)
#define forup(i,s,e) for(register ll i=(s);i<=(e);i++)
#define fordown(i,s,e) for(register ll i=(s);i>=(e);i--)
#define abs(x) (((x)^((x)>>63))-((x)>>63))
using namespace std;
#define gc getchar()
inline ll read(){
    ll x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const ll N=2e5+5,inf=0x3f3f3f3f;
ll t,n;
char b[N];
bool a[N],c[N*2];
ll mymod(ll a,ll b){
    if(a<0) a+=((-a+b-1)/b)*b;
    return a%b;
}
signed main(){
    t=read();n=read();
    scanf(" %s",b+1);
    forup(i,1,n){
        a[i]=b[i]-'0';
    }
    while(t){
        ll kk=t&-t;
        t-=kk;
        forup(i,1,n){
            c[i]=c[n*2+2-i]=a[i];
        }
        forup(i,1,n){
            a[i]=c[mymod(i+kk,n*2+2)]^c[mymod(i-kk,n*2+2)];
        }
    }
    forup(i,1,n){
        printf("%d",a[i]);
    }
}

进化（D.cpp 1S 512M）

题解

code

Comments