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;
}