Educational Codeforces Round 127（CF1671 D~E）题解-526互联

D. Insert a Progression

可以瞪出来的一个结论就是当我们在位置 \(p\) 插入了一个数 \(x\) 时，如果存在一对 \(l,r\) 满足 \(l<p\)，\(r>p\) 且 \(x\in[a_l,a_r]\)，那么我们插入的这个 \(x\) 就不会对序列的答案产生任何影响。

同时我们还注意到，插入 \(1\) 到 \(x\) 只会使得序列的答案增大而不会减小。

考虑插入 \(1\) 和 \(x\) 之后剩下的数可以插在它们之间从而不产生贡献，因此只需要为 \(1\) 和 \(x\) 找到最优的插入位置即可。

时间复杂度 \(O(n)\)，代码懒得写了（。

E. Preorder

题目链接

考虑 dp，设 \(f_u\) 表示以 \(u\) 为根的子树内能得到多少种不同的先序序列，直接的想法是根据乘法原理 \(f_u=f_{ls}\times f_{rs}\) 转移，然后考虑交换操作产生的影响，如果左右两棵子树不同构（注意这里同构的定义为：存在一种交换方式，使得两棵树结构相同），那么交换两棵子树也会产生相同的贡献，此时就有 \(f_u=2\times f_{ls}\times f_{rs}\)。

现在的问题就是判断子树同构，因为是个满二叉树，你可以考虑胡编一个哈希解决，时间复杂度 \(O(2^n)\)。

但其实没必要，子树同构等价于它们字典序最小的先序串相同，直接暴力维护这个东西即可，上界大概是 \(O(n2^n)\)。

#include<bits/stdc++.h>
#define int long long
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rof(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int N=5e5+5;
const int mod=998244353;
int n,ls[N],rs[N],f[N];
string hsh[N];
char s[N];
void dfs(int now){
    if(!ls[now]||!rs[now]){
        hsh[now]=s[now];f[now]=1;
        return;
    }
    dfs(ls[now]);dfs(rs[now]);
    hsh[now]=s[now];
    f[now]=f[ls[now]]*f[rs[now]]%mod;
    if(hsh[ls[now]]!=hsh[rs[now]]) f[now]=f[now]*2%mod;
    if(hsh[ls[now]]<hsh[rs[now]]) hsh[now]+=hsh[ls[now]]+hsh[rs[now]];
    else hsh[now]+=hsh[rs[now]]+hsh[ls[now]];
}
void Main(){
    cin>>n>>(s+1);n=(1ll<<n)-1;
    For(i,1,n){
        if((i<<1)<=n) ls[i]=i<<1;
        if((i<<1|1)<=n) rs[i]=i<<1|1;
    }
    dfs(1);cout<<f[1]<<'\n';
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T=1;//cin>>T;
    while(T--) Main();
    return 0;
}