题目描述
模拟季后赛。
已知有(1 << k)个队伍，team1实力最强，team2实力第2强，以此类推。赛制就是按照起始每个队伍的顺序开始两两对决，输的队伍直接淘汰，赢得进入下一轮，如下图所示，最终要求所有的队伍的位次按照右图的place（例如在n=8的时候，第一轮要淘汰5 6 7 8 第二轮要淘汰3 4，第三轮淘汰2）。现在给定的输入仅确定了部分位置的起始队伍是哪个，例如a[2] = 5，代表team5的初始位置确定了，为2，a[i]=-1代表第i个起始位置没有确定下是哪支队伍。求安排其余未确定队伍的初始位置后满足题意的方案数。
(模拟 + 组合数学计数) $O(n)$
直接模拟每一轮的对决，在特定的一轮，假设当前有n支队伍，按照题目要求，可以知道的是这一轮编号n/2+1到 n的队伍会淘汰，编号1到n/2的队伍晋级。那么问题转化为了，求这一轮要淘汰的队伍的所有确定位置的方案数量。
可以发现，当前两两对决的队伍构成了n/2个集合：
$\lbrace1, 2\rbrace, \lbrace3, 4\rbrace, … ,\lbrace n-1, n\rbrace$
如果编号n/2到n的队伍中已经确定了起始位置的两支队伍位于同一个集合，则输出0，因为本该淘汰的队伍会晋级，不符合题意。如果没有出现这样的情况，则对于所有的n/2个集合，必然有一个是编号为1到n/2和一个编号为n/2+1到n。那么只需要考虑编号n/2+1到n的队伍如何安排顺序，假设有其中有k个队伍是未定顺序的那么$res = res * k!$。同时，对于每一个集合，如果晋级的队伍位置没有定，那么被淘汰的队伍可以有两个方案（假设晋级的和淘汰的编号分别为$a, b$，则有$\lbrace a, b\rbrace$ 和$\lbrace b, a\rbrace$两种）。这时需要$res = res * 2$
时间复杂度
模拟了整个过程 时间复杂度是$O(n)$
C++ 代码
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define input_fast std::ios::sync_with_stdio(false);std::cin.tie(0)
const int mo = 998244353;
typedef long long ll;
const int N = (1 << 19) + 10;
int n, a[N], k, pos[N], next_pos[N], na[N];
bool vis[N];
ll fac[N];
void init() {
fac[0] = 1;
fac[1] = 1;
for (int i = 2; i < N; i ++) fac[i] = fac[i - 1] * i %mo;
}
void solve() {
init();
cin >> k;
n = (1 << k);
for (int i = 1; i <= n; i ++) {
cin >> a[i];
if (a[i] != -1) {
pos[a[i]] = i;
a[i] = 0;
} else {
a[i] = 1; //a[i] 代表位置i是否确定了队伍，1代表已经确定了放在这个位置的队伍，0 代表这个位置可以自己选择队伍放进去
}
}
ll res = 1;
while (n > 1) {
for (int i = 1; i <= n / 2; i ++) {
na[i] = a[i * 2 - 1] + a[i * 2]; //下一轮的第i组中对决的队伍有多少未确定的队伍
}
for (int i = 1; i <= n; i ++) {
next_pos[i] = (pos[i] + 1) / 2;
}
for (int i = 1; i <= n / 2; i ++) vis[i] = false;
int cnt = 0; // 这一轮被淘汰的队伍中 未确定顺序(seed)的队伍数量
for (int i = n / 2 + 1; i <= n; i ++) {
if (next_pos[i] == 0) {
cnt ++;
continue;
}
if (vis[next_pos[i]]) { //本轮 确定了起始位置(seed)的 且 要被淘汰 的队伍，如果其中有两支队伍进入下一轮的同一组，则输出0，因为不满足题意。
cout << 0;
return;
}
vis[next_pos[i]] = true;
}
res = res * fac[cnt] % mo;
for (int i = 1; i <= n / 2; i ++) {
if (!vis[i]) res = res * na[i] % mo, na[i] --; //vis[i] == false 代表下一轮第i组 中 在本轮被淘汰的队伍没有确定是哪支队伍
}
for (int i = 1; i <= n / 2; i ++) pos[i] = next_pos[i];
for (int i = 1; i <= n / 2; i ++) a[i] = na[i];
n /= 2;
}
cout << res;
}
int main() {
// freopen("C:/Users/14842/CLionProjects/cf/in.txt", "r", stdin);
// freopen("C:/Users/14842/CLionProjects/cf/out.txt", "w", stdout);
// int tt;
// cin >> tt;
// while (tt --)
solve();
return 0;
}
