【题解】CF1569E Playoff Restoration

· · 题解

因为每场比赛都是编号相邻的两个队伍 pk，因此考虑将这个过程看成线段树 pushup 。

任意一棵 n 个节点的树都可以看成一棵 n-1 个节点的树添加叶子构造而成。

因此有 $n$ 个叶子节点的二叉树，节点数是 $2n-1$ 。

因此，一共会 pushup 2^k-1 次。

一个直接的暴力做法就是枚举这 2^k-1 次 pushup 的结果。

对于 2^{32} 这种级别的计算量，我们考虑将其折半，也就是 meet in the middle。

注意到，[1,2^{k-1}],(2^{k-1},2^k] 在最后一次 pushup （也就是 pushup 根节点）前的状态互不影响，并且我们只关心最终的哈希值。

因此我们可以考虑分别枚举两边的 pushup 状态，开两个哈希表存储前一半的哈希值与排名，分别最后一个元素排名为 1/2 的情况。

枚举后一半时在哈希表中查询即可。

对于计算哈希值，枚举每个位置在第几轮淘汰即可，代码很好写。

#include <bits/stdc++.h>

#define rep(i,l,r) for (int i = l; i <= r; i++)
#define per(i,r,l) for (int i = r; i >= l; i--)
#define fi first
#define se second
#define prt std::cout
#define gin std::cin
#define edl std::endl
#define int long long

namespace wxy{

const int N = 50,mod = 998244353;

int k,n,m,A,H,power[N];

std::map<int,std::vector<int>> mp[2];

int d[10];

int fpow(int a,int b) {
    int res = 1;
    for (; b ; b >>= 1) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}

inline void main(){
    #ifndef ONLINE_JUDGE
        freopen("in.in","r",stdin);
        freopen("out.out","w",stdout);
    #endif
    per(i,5,1) d[i] = fpow(2,i-1) + 1;
    d[0] = 1; power[0] = 1;
    gin >> k >> A >> H; n = (1 << k); m = (1 << k - 1);
    rep(i,1,40) power[i] = power[i-1] * A % mod;
    for (int S = 0; S < (1 << m); ++S) {
        std::vector<int> p; int hash = 0;
        for (int i = 1; i <= m; i++) {
            int u = i + m - 1,t = k;
            while (t) {
                if (((S >> (u >> 1)) & 1) ^ (u & 1)) break;
                u >>= 1; --t;
            }
            hash = (hash + i * power[d[t]] % mod) % mod;
            p.push_back(d[t]);
        }
        mp[S&1][hash] = p;
    }
    for (int S = 0; S < (1 << m); ++S) {
        std::vector<int> p; int hash = 0;
        for (int i = 1; i <= m; i++) {
            int u = i + m - 1,t = k;
            while (t) {
                if (((S >> (u >> 1)) & 1) ^ (u & 1)) break;
                u >>= 1; --t;
            }
            hash = (hash + (i + m) * power[d[t]] % mod) % mod;
            p.push_back(d[t]);
        }
        int val = (H - hash + mod) % mod;
        if (mp[S&1^1].count(val)) {
            std::vector<int> pre = mp[S&1^1][val];
            for (int j = 0; j < pre.size(); j++) prt << pre[j] << " ";
            for (int j = 0; j < p.size(); j++) prt << p[j] << " ";
            return;
        }
    }
    puts("-1");
}

}signed main(){wxy::main(); return 0;}