题解：CF1837E Playoff Fixing

Shellchen · 2026-10-20 21:26:35 · 题解

这题不错，mark 一下。

先把所有非 -1 的数减去 1，便于处理，并且之后数组改为 0-index。

容易发现 \ge 2^{k-1} 的东西第一轮都要没掉。因此对于所有 i，a_i 和 a_{i\oplus 1} 中一定要有恰好一个 \ge 2^{k-1}。

考虑这么一个做法：扫一遍整个序列，并记录操作一次之后的序列 b，对所有 a_i 和 a_{i\oplus 1} 做如下处理：

• 如果均不是 -1：在 b 中插入胜者即可。注意如果没有满足恰好一个 \ge 2^{k-1} 那么要直接输出 0。
• 如果恰有一个 -1，且另一个 \ge 2^{k-1}：在 b 中插入一个 -1（因为你填的一定 <2^{k-1} 且会获胜，之后再计算）。
• 如果恰有一个 -1，且另一个 <2^{k-1}：在 b 中插入该数。
• 如果都是 -1：在 b 中插入一个 -1，并使答案乘上 2（因为可以交换这两个数）。

另外可以发现所有应该填败者的 -1 是可以随便调换败者的顺序的，因此答案要乘上一个应该填败者的 -1 个数（也就是后面两种情况的出现次数）的阶乘。

完成这个过程后，对 b 再次处理，直到序列长度为 1 为止。b 的长度为 a 的长度的一半，因此 k 要减去 1。

分析复杂度：设复杂度为 T(k) 则 T(k)=T(k-1)+2^k，也就是 O(2^k) 的（或者关于序列长度线性）。 :::success[code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ui unsigned int
#define i128 __int128_t
#define u128 __uint128_t
#define i16 short
#define u16 unsigned i16
#define fi first
#define se second
#define pii pair<int,int>
#define lowbit(x) ((x)&(-(x)))
#ifdef int
#define i32 signed
#define u32 unsigned
#define inf (int)(1e18)
#define popc(x) __builtin_popcountll(x)
#define ctz(x) __builtin_ctzll(x)
#define clz(x) __builtin_clzll(x)
#else
#define ll long long
#define ull unsigned ll
#define inf (int)(1e9)
#define infl (int)(1e18)
#define popc(x) __builtin_popcount(x)
#define ctz(x) __builtin_ctz(x)
#define clz(x) __builtin_clz(x)
#define popcl(x) __builtin_popcountll(x)
#define ctzl(x) __builtin_ctzll(x)
#define clzl(x) __builtin_clzll(x)
#define pll pair<ll,ll>
#endif
#define double long double
#define sqrt(x) sqrtl(x)
#define cbrt(x) cbrtl(x)
#define pow(x,y) powl(x,y)
#define sin(x) sinl(x)
#define cos(x) cosl(x)
#define tan(x) tanl(x)
#define push emplace
#define pb emplace_back
#define pf emplace_front
#define ppb pop_back
#define ppf pop_front
const int N=1e6+10,mod=998244353;
int a[N],b[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int k;
    cin>>k;
    for(int i=1;i<=(1<<k);i++) cin>>a[i],(a[i]==-1?a[i]:a[i]--);
    int ans=1;
    for(int tk=k;tk>=1;tk--)
    {
        int n=(1<<tk);
        int cc=0;
        for(int i=1;i<=n;i+=2)
        {
            if(a[i]!=-1&&a[i+1]!=-1)
            {
                if(!((a[i]^a[i+1])>>tk-1&1))
                {
                    cout<<0;
                    return 0;
                }
                if(a[i]>>tk-1&1) b[(i+1)/2]=a[i+1];
                else b[(i+1)/2]=a[i];
                continue;
            }
            if(a[i]==-1&&a[i+1]==-1) b[(i+1)/2]=-1,cc++,(ans*=2*cc)%=mod;
            else
            {
                if(a[i]==-1) swap(a[i],a[i+1]);
                if(a[i]>>tk-1&1) b[(i+1)/2]=-1;
                else b[(i+1)/2]=a[i],cc++,(ans*=cc)%=mod;
            }
        }
        for(int i=1;i*2<=n;i++) a[i]=b[i];
    }
    cout<<ans;
    return 0;
}

:::