2022.07.22 模拟赛

别点，没题解。

T3 cal

题意

题解

Subtask 1

我不知道有没有方法啊，反正我是手玩的！

Subtask 2

迫真 A+B Problem.

令 $w=64$，观察这个怪异的时间计算方式，它似乎对线段树非常利好：建树的复杂度变成了 $O(\log w)$。

考虑竖式加法（草）的过程：

$\begin{array}{lll} &&1&0&0&1\\ +&{\ }_1&1_0&0_1&1_1&1\\ \hline &1&0&1&0&0 \end{array}$

为方便起见我用 $a_i=0/1$ 表示 $A$ 从低到高第 $i$ 个二进制位，$b_i$ 同理，$c_i$ 表示竖式加法第 $i$ 个位置是否有进位（比如上式的 $C=(1011)_2$），那显然有 $A+B=A\oplus B\oplus (C\ll 1)$，因为竖式最下面的数肯定是上面三个数的异或。

那我们考虑如何计算这个 $C$，它显然是递推得到的。我的主题思路大概就是从线段树出发，如果这个递推可以被写成有结合律的形式（类比于动态 DP），那么就可以 $O(\log w)$ 建出线段树，$O(\log w)$ 查询出这 $w$ 个点值。

那观察这个递推：

• 若 $a_i=b_i=1$，则必然进位，$c_i=1$。
• 若 $a_i+b_i=1$，进位当且仅当 $c_{i-1}=1$，则 $c_i=c_{i-1}$。
• 若 $a_i=b_i=0$，不可能进位。

用位运算表达出来（为了看的清楚就写字母了）：$c_i = (c_{i-1}\operatorname{and} (a_i \operatorname{or} b_i) )\operatorname{or} (a_i \operatorname{and}b_i)$。

不难发现由 $c_{i-1}\to c_i$ 是与了一个之后或了一个。若经过一系列这样的变换之后有 $c_l \to c_r$，$c_r$ 只可能三种情况：必为 $0$，必为 $1$，必为 $c_l$。

这样就可以挂上线段树了！节点 $[l,r]$ 上维护 $s_0$、$s_1$ 表示从 $l$ 走到 $r$ 后，此数是否必为 $0$ / 为 $1$，显然具有结合律。这样子求出 $C$ 以后，用同样的分治过程把这些分开的二进制位合成一个整数即可（因为线段树要把每一位拆开比较好建！）。

考场代码，但由于比较仓促写的就比较糟糕：

查看代码

#include<bits/stdc++.h>
#define pbk emplace_back
#define FOR(i,a,b) for(int i=a,i##i=b;i<=i##i;++i)
using namespace std;
typedef unsigned long long ull;
const int N=407;
ull a[N],C=400,L=9;
void NOT(int x,int y){printf("NOT %d %d\n",x,y),a[x]=~a[y];}
void LSH(int x,int y){printf("LSH %d %d\n",x,y),a[x]<<=y;}
void RSH(int x,int y){printf("RSH %d %d\n",x,y),a[x]>>=y;}
void SET(int x,int y){printf("SET %d %d\n",x,y),a[x]=a[y];}
void XOR(int x,int y,int z){printf("XOR %d %d %d\n",x,y,z),a[x]=a[y]^a[z];}
void AND(int x,int y,int z){printf("AND %d %d %d\n",x,y,z),a[x]=a[y]&a[z];}
void OR(int x,int y,int z){printf("OR %d %d %d\n",x,y,z),a[x]=a[y]|a[z];}
int b[N],A[N],B[N],And[N],Or[N],s0[N],sif[N];
void solve(int l,int r){
    int mid=(l+r)/2;
    if(l==r){
        AND(s0[l],Or[l],s0[l]),OR(s0[l],s0[l],And[l]);
        AND(sif[l],Or[l],sif[l]),OR(sif[l],sif[l],And[l]);
        return;
    }
    solve(l,mid),solve(mid+1,r);
    FOR(i,mid+1,r){
        AND(4,s0[mid],s0[i]);
        AND(5,sif[mid],s0[i]);
        OR(s0[i],4,sif[i]);
        OR(sif[i],sif[i],5);
    }
}
void build(int l,int r){
    if(l==r){
        SET(A[l],sif[l]);
        if(l!=63)LSH(A[l],l+1);
        else A[l]=++L;
        return;
    }
    int mid=(l+r)/2;
    build(l,mid),build(mid+1,r);
    OR(A[l],A[l],A[mid+1]);
}
int main(){
    freopen("dt.in","r",stdin);
    freopen("cal2.out","w",stdout);
    cin>>a[1]>>a[2];
    cerr<<a[1]+a[2]<<endl;
    XOR(3,1,2),NOT(400,400),RSH(400,63);
    FOR(i,0,63)b[i]=--C,SET(C,400),LSH(b[i],i);
    FOR(i,0,63)A[i]=++L,AND(L,1,b[i]),RSH(L,i);
    FOR(i,0,63)B[i]=++L,AND(L,2,b[i]),RSH(L,i);
    FOR(i,0,63)And[i]=++L,AND(L,A[i],B[i]);
    FOR(i,0,63){
        Or[i]=B[i],OR(Or[i],A[i],B[i]);
        sif[i]=++L,s0[i]=A[i],SET(s0[i],400);
    }
    solve(0,63),build(0,63);
 //   cerr<<a[3]<<endl;
    XOR(1,3,A[0]);
    cerr<<a[1];
    return 0;
}