codeforce每日一题链接

题目描述

题意太长，可以看原题。

样例

输入样例1

2
1 2 3 4

输出样例1

0

输入样例2

2
1 3 4 2

输出样例2

1

输入样例3

1
-1 -1

输出样例3

2

算法

(枚举) $O(n*log(n))$

我们每次只考虑后面n/2个队伍填到哪个位置，因为后面的队伍是一定要和前面n/2个队伍匹配的，所以我们找出后面n/2支队伍有哪些没有填，如果发现后面的队伍和后面的队伍打了，直接输出0就好了。将找出来的队伍以全排列的形式乘入答案中。然后再找出哪些位置有空缺的，如果发现当前位置是有空缺的，那么被分配到当前韦德队伍还挑选位置，所以答案乘上这个位置空缺的位置次数，填上后将这个位置的次数减1。

C++ 代码 (参考的jiangly的代码)

//  https://www.acwing.com/blog/content/34755/

#include<bits/stdc++.h>

#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;

const int N = 2e6+10, M = N * 2, INF = 0x3f3f3f3f, mod = 998244353;

int n, m;
LL f[N];

void init()
{
    f[0] = 1;
    for(int i=1;i<=n;i++) f[i] = f[i-1] * i % mod;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n;
    n = 1 << n;
    init();
    vector<int> a(n, -1);
    vector<int> s(n, 1);

    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        if(x != -1){
            x--;
            a[x] = i;
            s[i] = 0;
        }
    }

    LL res = 1;
    while(n > 1)
    {
        vector<bool> st(n/2, 0);
        vector<int> g(n/2, 0);
        for(int i=0;i<n/2;i++) g[i] = s[i*2] + s[i*2+1];
        for(int i=0;i<n;i++){
            if(a[i]!=-1) a[i] /= 2;
        }
        LL ans = n / 2;
        for(int i=n/2;i<n;i++){
            if(a[i] != -1){
                if(st[a[i]]){
                    cout<<0<<endl;
                    return 0;
                }
                st[a[i]] = true;
                ans --;
            }
        }

        res = res * f[ans] % mod;
        for(int i=0;i<n/2;i++){
            if(!st[i]){
                res = res * (g[i]--) % mod;
            }
        }
        a.resize(n/2);
        s = g;
        n/=2;
    }

    cout<<res<<endl;

    return 0;
}