AGC025F Addition and Andition

给定两个长为 $n,m$ 的二进制串 $x,y$，有 $k$ 次操作，每次令 $x,y$ 同时加上 $x\&y$，求最后的 $x,y$。

$1 \le n,m,k \le 10^6$。

直接模拟可以做到 $O((n+m)k)$。

可以手玩几组观察性质，发现只会移动 $x_i=y_i=1$ 的位置，并且它们之间是独立的，简单来说就是不会撞到一起。考虑从高位到低位考虑这样的位置（因为高位的“足迹”会对低位产生影响）。

对于 $x_i=y_i=1$ 的 $i$，按 $i+1$ 位分讨

• $x_{i+1}=y_{i+1}=0$，相当于 $i$ 位的 $1$ 移动一步。

• $x_{i+1}=y_{i+1}=1$，不可能存在。

• 其他，当前位的 $1$ 会向前跳跃几步（根据连续 $1$ 的个数）。

对于第三种情况，可以直接将当前位清空，下一位加 $1$，在下一位再处理进位，在当前位步数加 $1$（进位的位步数不加）。

发现每次进行进位 $1$ 的个数都会减少，那么进位只会进行 $O(n+m)$ 次。而第一种情况很好缩在一起，那么得出了 $O(n+m+k)$ 的模拟做法。

具体的，从高位到低位枚举，将 $x/y$ 非空的位加入栈中，当枚举到 $x=y=1$ 的位时进行上述模拟，具体细节见代码。

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
const int N=1e6+100,INF=1e9;
#define gc getchar()
#define rd read()
inline int read(){
    int x=0,f=0; char c=gc;
    for(;c<'0'||c>'9';c=gc) f|=(c=='-');
    for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+(c^48);
    return f?-x:x;
}

int n,m,K,a[N*2],b[N*2],sta[N*2],tp=0;
char s[N],t[N];
vector<int> vc;

int main(){

    n=rd,m=rd,K=rd,scanf("%s %s", s+1, t+1);
    reverse(s+1,s+n+1),reverse(t+1,t+m+1);
    for(int i=1;i<=max(n,m);++i) a[i]=(i<=n?s[i]-'0':0),b[i]=(i<=m?t[i]-'0':0);
    sta[tp=1]=INF;
    for(int i=max(n,m);i>=1;--i){
        if(!a[i]&&!b[i]) continue;
        else if(a[i]&&b[i]){
            vc={};
            for(int j=i,c=K;;){
                vc.pb(j);
                for(;tp&&sta[tp]<=j;--tp);
                if(a[j]==1&&b[j]==1&&c){
                    if(tp&&sta[tp]==j+1) a[j]=b[j]=0,++a[j+1],++b[j+1],--c,++j;
                    else{ a[j]=b[j]=0; int jp=min(c,sta[tp]-j-1); c-=jp,j+=jp; a[j]=b[j]=1; }
                }
                else if(a[j]>1||b[j]>1){
                    a[j+1]+=a[j]/2,a[j]&=1;
                    b[j+1]+=b[j]/2,b[j]&=1;
                    ++j;
                }
                else break;
            }
            reverse(vc.begin(),vc.end());
            for(int v:vc) if(a[v]||b[v]) sta[++tp]=v;
        }
        else sta[++tp]=i;
    }

    reverse(a+1,a+n+K+1);
    for(int i=1,flag=0;i<=n+K;++i){
        if(!a[i]&&!flag) continue;
        printf("%d", a[i]); flag=1;
    }
    puts("");
    reverse(b+1,b+m+K+1);
    for(int i=1,flag=0;i<=m+K;++i){
        if(!b[i]&&!flag) continue;
        printf("%d", b[i]); flag=1;
    }
    puts("");

    return 0;
}