03801202-AGC022

C

给定序列 $A$ ，通过若干次操作使其变为序列 $B$ 。对于每次操作，选择一个正整数 $k$ ，对于每个数选择将其变为 $a_{i} (\mod k)$ 或不变，这次操作代价 $2^{k}$ 。总代价为所有操作代价和，球最小总代价

注意这个 $2^{k}$ 的代价，其意味着从高位到地位贪心

然后对每个 $k$ 建图判断一下

const int N=55;
int n,f[N][N],a[N],b[N];

inline bool check(ll sta){
    for(rei i=0;i<N;++i) for(rei j=0;j<N;++j) f[i][j]=i==j ? 1 : 0;
    for(rei i=0;i<N;++i) for(rei j=1;j<=i;++j) if(sta & (1ll<<j)) f[i][i%j]=1;
    for(rei k=0;k<N;++k) for(rei i=0;i<N;++i) for(rei j=0;j<N;++j) f[i][j]|=(f[i][k] & f[k][j]);
    bool ret=true;
    for(rei i=1;i<=n;++i) if(!f[ a[i] ][ b[i] ]){ ret=false; break;}
    return ret;
}

int main(){
    scanf("%d",&n);
    for(rei i=1;i<=n;++i) scanf("%d",&a[i]);
    for(rei i=1;i<=n;++i) scanf("%d",&b[i]);
    ll sta=(1ll<<38)-2;
    if(!check(sta)){ return puts("-1"),0;}
    for(rei i=37;i;--i){
        ll tmp=sta^(1ll<<i);
        if(check(tmp)){ sta=tmp;}
    }
    printf("%lld\n",sta);
    getchar(),getchar();
    return 0;
}

D

$N$ 个商场，第 $i$ 个在数轴的 $x_{i}$ ，需要花费连续的 $t_{i}$ 时间购物。一趟火车在 $0, L$ 处往返，行驶一单位长度用一单位时间，在 $0$ 时于 $0$ 处上车，只有在 $商场， 0 ， L$ 处才可下车，求在每个超市购物后返回 $0$ 处的最少时间

有一个神仙思路：

对于每个 $t_{i}$ ，先 $% 2 \times L$ ，再把 $2 \times L \times n$ 加到答案里

考虑一个点，如果从左边进只需要到达依次端点就看作左括号，从右边进只需要依次达到端点就看作右括号

先默认每个点贡献都是 $2 \times L$ ，那么左右括号匹配时则可以减少 $2 \times L$

某些点可以看作左/右括号，此时考虑最大化匹配数

有性质：当一个节点开始时固定作为左括号，则后面一定没有固定作为右括号的，所以不会有两个固定的括号匹配。

贪心即可

const int N=3e5+10;
int n,len,x[N],t[N],l[N],r[N],ans;

int main(){
    scanf("%d%d",&n,&len);
    for(rei i=1;i<=n;++i) scanf("%d",&x[i]);
    for(rei i=1;i<=n;++i) scanf("%d",&t[i]);
    for(rei i=1;i<=n;++i){
        ans+=t[i]/(2*len); t[i]%=2*len;
        if(!t[i]){ --ans; continue;}
        l[i]=(t[i]<=x[i]*2);
        r[i]=(t[i]<=(len-x[i])*2);
    }
    rei lim=n,L=0,R=0;
    ans+=n+1-r[n];
    for(rei i=1;i<n;++i){
        if(!l[i] && !r[i]) continue;
        if(!r[i]){ lim=i; break;}
        if(!l[i] && L) --L,--ans;
        else if(l[i]) ++L;
    }
    for(rei i=n-1;i>=lim;--i){
        if(!l[i] && !r[i]) continue;
        if(!l[i]) break;
        if(!r[i] && R) --R,--ans;
        else if(r[i]) ++R;
    }
    ans-=(L+R)>>1;
    printf("%lld\n",2ll*ans*len);
    getchar(),getchar();
    return 0;
}

E

一个奇数长度的 $01$ 串 $s$ ，其中若干位置是符号 $?$ ，每次将 $3$ 个连续的字符替换成着三个数的中位数，有多少种方案将 $?$ 替换成 $0 / 1$ 后再进行 $\frac{n - 1}{2}$ 次操作后字符串为 $1$

首先考虑没有 $?$ 的情况，考虑其是否合法

维护一个栈，其中包括一段连续的 $0$ 和一段连续的 $1$

加入 $0$
- 栈顶 $0$ ：若栈内 $2$ 个 $0$ ，则替换成一个 $0$ ，否则入栈
- 栈顶 $1$ ：直接入栈
加入 $1$
- 栈顶 $0$ ：弹出栈顶的 $0$ ，相当于抵消
- 栈顶 $1$ ：若栈内只有一个 $1$ 则入栈，否则不管

那么最后只要 $n u m_{1} > n u m_{0}$ 则合法

简化一下栈内部：发现 $0, 1$ 的个数只可能是 $0 \sim 2$ ，设 $f_{i, a, b}$ 表示第 $i$ 位时，栈内有 $a$ 个 $1$ ， $b$ 个 $0$ 的方案数

有转移：

s [i + 1] = 0 时 {\begin{cases} f_{i + 1, a, 1} + = f_{i, a, 2} + f_{i, a, 0} \\ f_{i + 1, a, 2} + = f_{i, a, 1} \end{cases}

s [i + 1] = 1 时 {\begin{cases} f_{i + 1, a, b - 1} + = f_{i, a, b} \\ f_{i + 1, 1, 0} + = f_{i, 0, 0} \\ f_{i + 1, 2, 0} + = f_{i, 1, 0} + f_{i, 2, 0} \end{cases}

s [i + 1] = ? 时 {\begin{cases} s [i + 1] = 1 时 \\ s [i + 1] = 0 时 \end{cases}

const int N=3e5+100;
const int mod=1e9+7;
int n,ans;
int f[N][3][3];
char s[N];

inline void fix(int &x){ x>=mod ? x-=mod : 0;}

int main(){
    scanf("%s",s+1); n=strlen(s+1);
    f[0][0][0]=1;
    for(rei i=0;i<n;++i){
        if(s[i+1]!='1')
            for(rei a=0;a<=2;++a){
                fix(f[i+1][a][1]+=f[i][a][2]);
                fix(f[i+1][a][1]+=f[i][a][0]);
                fix(f[i+1][a][2]+=f[i][a][1]);
            }
        if(s[i+1] != '0'){
            for(rei a=0;a<=2;++a){
                fix(f[i+1][a][0]+=f[i][a][1]);
                fix(f[i+1][a][1]+=f[i][a][2]);
            }
            fix(f[i+1][1][0]+=f[i][0][0]);
            fix(f[i+1][2][0]+=f[i][1][0]);
            fix(f[i+1][2][0]+=f[i][2][0]);
        }
    }
    for(rei a=0;a<=2;++a) for(rei b=0;b<=a;++b) fix(ans+=f[n][a][b]);
    printf("%d\n",ans);
    getchar(),getchar();
    return 0;
}

F

$x = 10^{100}$ ，数轴上有 $n$ 个点，点 $i$ 的坐标为 $x_{i}$ ， $n - 1$ 次操作，每次选择两点 $A, B$ ，将 $A$ 移动到 $B$ 的对称点并删去 $B$ ，求最后剩的数取值的方案数

当 $关于 B 对称的 A$ 变成 $2 B - A$ 时，即 $B 被消掉$ 时，将 $A$ 视作 $B$ 的父亲，最终形成一颗具有儿子相对顺序的树，如此最终剩下来的点就是根节点

将一个点 $A$ 的贡献视作 $2^{d_{A}} \times c_{A} \times x_{A}$ ，其中 $x_{A}$ 视作未知数， $d_{A}$ 为节点 $A$ 深度， $c_{A}$ 为正负号

考虑到 $x_{i}$ 极大且 $x_{i + 1} - x_{i}$ 也极大，那么不会出现点贡献相互抵消，那么只需要考虑前面的系数即可

深度显然易得，考虑如何求 $c_{i}$

这里采取间接确定每一项的符号，即，对于点 $i$ 的字节点 $s o n_{1}, s o n_{2}, \dots s o n_{k}$ ，已知点 $i$ 的符号，观察 $k$ 个子节点符号与 $i$ 的关系

当 $i$ 再向上与 $f a_{i}$ 连边时，相当于有 $2 \times v a l_{i} - v a l_{f a}$ ，而 $s o n_{i}$ 又有贡献 $2 \times v a l_{s o n} - 2 \times v a l_{i}$ ，所以连边后 $i$ 与 $s o n_{i}$ 的正负号会同时取反

而当 $s o n_{i}$ 连向 $i$ 时，对于 $s o n_{i}$ ，其实质相当于 $\times 2$ ，而对于 $i$ ，其实质为 $\times - 1$

那么有结论：当且仅当节点 $v$ 有奇数个字节点时，其符号与父节点不一样

考虑 $d p$ 解决：

设 $f_{i, j}$ 表示放了 $i$ 个节点，最后一层有 $j$ 个节点的儿子数量为奇数时的方案数

为了方便将 $c_{i}$ 差分，与 $f a$ 相同记作 $1$ ，不同记作 $- 1$ ，转移时仅关心下一层与 $f a$ 相同/不同的数量

对于点 $v$ 有 $k$ 个儿子，若不考虑儿子的儿子的影响，应该有 $⌊ \frac{k}{2} ⌋$ 个儿子的 $c$ 与 $v$ 不同

设下一层长出 $k$ 个节点，其中 $\frac{k - j}{2}$ 个点正负与父亲不同(此时kj奇偶性不同则跳过)

设考虑儿子的儿子的影响后，点 $v$ 有 $x$ 个儿子与之正负不同，那么就有 $| x - \frac{k - j}{2} |$ 个节点( $s o n_{v}$ )的正负性需要修正，即，下一层中的点的儿子个数为奇数的节点数

const int N=55;
const int mod=1e9+7;
ll c[N][N],f[N][N]; int n;

int main(){
    scanf("%d",&n);
    for(rei i=0;i<=n;++i){
        c[i][0]=1;
        for(rei j=1;j<=i;++j) c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
    }
    f[1][0]=f[1][1]=n;
    for(rei i=1;i<n;++i) for(rei j=0;j<=i;++j) for(rei k=(!j ? 2 : j);i+k<=n;k+=2){
        rei t=(k-j)>>1;
        for(rei x=0;x<=k;++x) (f[i+k][abs(x-t)]+=f[i][j]*c[n-i][k]%mod*c[k][x]%mod)%=mod;
    }
    printf("%lld\n",f[n][0]);
    getchar(),getchar();
    return 0;
}