AGC025F Addition and Andition

AGC025F

有两个长度为$n$和$m$的二进制数$x$和$y$。要做如下操作$k$次：

$x+=x\&y,y+=x\&y$

问$k$次之后$x$和$y$分别是多少。

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

补很久前的题解。

模拟一下暴力：操作$k$次，每次操作就是，从高位往低位，如果两个串对应位上的数为$(1,1)$，那么将这两位清空并且向前进一位。

不妨改变一下枚举的顺序：从高位往低位，如果两个串对应为上数为$(1,1)$，做$k$次“向前移动”的操作（即当前位清空，如果前面为$(0,0)$，那么前面变成$(1,1)$，指针前移一位；如果前面为$(0,1)$，前面$x$对应位变成$1$，$y$对应位进位，若是存在形如$(100,011)$变成$(101,100)$的情况，那么指针移到前面那个$(1,1)$；前面不可能为$(1,1)$）。

用链表来维护状态相同的连续段。模拟即可。

势能分析，时间复杂度是对的：当前面有连续的$(0,0)$时，$O(1)$移动过去，不影响；然后遇到连续的$(0,1)$。当前面有连续的$(0,1)$时，可能越过这连续的$(0,1)$并且在前面创造了新的$(1,1)$（创造新的$(1,1)$：连续的$(0,1)$前有个$(1,0)$），但是同时意味着这一段连续的$(0,1)$变成$(0,0)$（最后一个除外，变成$(1,0)$)。如果我们把$(0,1)$连着$(1,0)$的位置个数定义为势能，那么时间复杂度就显然了。

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 1000010
int n,m,k;
char str[N];
int s[N],t[N];
struct Node{
    Node *pre,*suc;int s,n;
} *fir,*lst;
Node *ins(Node *p,int s,int n=1){
    Node *nw=new Node;*nw={
    p,p->suc,s,n};if (p->suc)p->suc->pre=nw;elselst=nw;p->suc=nw;return nw;
}
Node *check(Node *p){
    if (p->n==0 || p->pre && p->s==p->pre->s){
    p->pre->n+=p->n;p->pre->suc=p->suc;if (p->suc)p->suc->pre=p->pre;elselst=p->pre;return p->pre;}return p;
}
int ans[N*2],cnt;
void print(int w){
    bool bz=0;for (int i=cnt-1;i>=0;--i){
    bz|=ans[i]>>w&1;if (bz)putchar('0'+(ans[i]>>w&1));}if (bz==0)putchar('0');putchar('\n');
}
int main(){
    scanf("%d%d%d",&n,&m,&k);scanf("%s",str);for (int i=0;i<n;++i)s[i]=str[n-1-i]-'0';scanf("%s",str);for (int i=0;i<m;++i)t[i]=str[m-1-i]-'0';n=max(n,m);	fir=lst=new Node;*lst=(Node){
    NULL,NULL,0,1000000000};for (int i=n-1;i>=0;--i)if (s[i]==1 && t[i]==1){
    int z=k;Node *p=lst;while (z){
    while (1){
    Node *q=check(p);if (q==p) break;p=q;}if (p->s==0){
    if (p->n<=z){
    z-=p->n;p=p->pre;if (z==0)ins(p,3,1);}else{
    p->n-=z;Node *q=ins(p,0,z);ins(p,3,1);break;}}else{
    while (1){
    Node *q=check(p->pre);if (q==p->pre) break;p->pre=q;}int m=p->s;if (p->pre->s==0){
    p->s=0,p->n--;Node *q=ins(p,m^3,1),*r=ins(q,0,1);p->pre->n--;check(p->pre);ins(p->pre,m,1);check(p);break;}else{
    p->s=0,p->n--;Node *q=ins(p,m^3,1),*r=ins(q,0,1);p->pre->n--;p=p->pre;z--;check(p->suc);if (z==0)ins(p,3,1);p=check(p);}}}}elselst=ins(lst,s[i]|t[i]<<1,1);for (Node *p=lst;p!=fir;p=p->pre)for (int i=0;i<p->n;++i)ans[cnt++]=p->s;print(0),print(1);return 0;
}