这个题哎呀。。。细节超级多。。。
首先，我猜了一个结论。如果有一种排序方案是可行的，假设这个方案是 $S$ 。
那么我们把 $S$ 给任意重新排列之后，也必然可以构造出一组合法方案来。
于是我们就可以 $O(2^n)$ 枚举每个操作进不进行，再去判断，如果可行就 $ans$ += $|S|!$。
然而怎么判断呢？
我们按照操作种类从小到大操作。
假设我们现在在决策第 $i$ 种操作并且保证之前之后不需要进行种类编号 $< i$ 的操作。
那么我们只考虑那些位置在 $2^i+1$ 的位置的那些数。
我们先找到所有的非法位置，满足下列条件之一就是非法位置，设当前位置为 $pos$：
- 条件$1$：$A_{pos}$ 不能表示成 $a\times 2^i + 1$，其中 $a$ 为非负整数。
- 条件$2$：$A_{pos + 2^{i-1}} \ne A_{pos} + 2^{i-1}$。
满足以下三种情况之一即为无解：
- 如果有三个或以上个非法位置，那么显然就无解了。
- 如果没有非法位置，但是当前状态下必须要进行一次操作，那么无解。
- 如果有非法位置，但是当前状态下必须不进行操作，那么无解。
那么现在开始讨论：
当没有非法位置的时候，直接递归求解。
当只有一个非法位置的时候，交换 $A_{pos}$ 和 $A_{pos + 2^{i-1}}$，递归求解。
这里本来应该交换一个区间的，然而有用的其实只有 $A_{pos}$ 和 $A_{pos + 2^{i-1}}$ 这两个数。
因为其他的数字我们现在不会考虑，以后也更不用考虑了，反正保证是合法的，所以我们只交换这两个数。
当有两个非法位置的时候，设两个非法位置为 $pos_1$ 和 $pos_2$
我们把非法位置分两类：第一类是满足条件 $1$ 的，第二类是不满足条件 $1$ 但满足条件 $2$ 的。
- $type(pos_1) = 2$ && $type(pos_2) = 2$：可以有两种可能合法的交换：交换 $A_{pos_1}$ 和 $A_{pos_2}$ 或者交换 $A_{pos_1 + 2^{i - 1}}$ 和 $A_{pos_2 + 2^{i - 1}}$。
- $type(pos_1) = 2$ && $type(pos_2) = 1$：只有一种可能合法的交换：交换 $A_{pos_1 + 2^{i - 1}}$ 和 $A_{pos_2}$。
- $type(pos_1) = 1$ && $type(pos_2) = 2$：只有一种可能合法的交换：交换 $A_{pos_1}$ 和 $A_{pos_2 + 2^{i - 1}}$。
- $type(pos_1) = 1$ && $type(pos_2) = 1$：无解。
然后递归求解即可。注意每当交换完之后要判断原来的非法位置是否变合法了，如果还是非法的那么就直接判掉。
判断每个状态的复杂度：
$$\sum_{i=1}^{n}2^i\times\frac{2^n}{2^i} = \sum_{i=1}^{n}2^n = n\times 2^n$$
于是整个问题的复杂度就是：$O(n2^{2n})$ 的了。
然而常数很小很小，应该很难构造一组卡到上界的数据，所以跑得还是比较快的。。。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
#define N 12 + 5
#define SIZE 1 << 12 | 5 int n;
LL ans;
LL Fac[N];
int A[SIZE], Cnt[SIZE]; inline bool dfs(int state, int len)
{
if (len >> (n + )) return ;
int cnt = , pos_1, pos_2;
for (int i = ; i < ( << n); i += len)
{
int _i = i + (len >> );
if ((A[i] & (len - )) || A[_i] != A[i] + (len >> ))
{
cnt ++;
if (cnt == ) pos_1 = i;
else if (cnt == ) pos_2 = i;
else return ;
}
}
if ((state & ) == && cnt) return ;
if ((state & ) && !cnt) return ;
if (!cnt) return dfs(state >> , len << );
if (cnt == )
{
swap(A[pos_1], A[pos_1 + (len >> )]);
bool ok = dfs(state >> , len << );
swap(A[pos_1], A[pos_1 + (len >> )]);
return ok;
}
if (cnt == )
{
bool ok = ;
if ((A[pos_1] & (len - )) && (A[pos_2] & (len - ))) return ;
else if (A[pos_1] & (len - ))
{
swap(A[pos_1], A[pos_2 + (len >> )]);
if (A[pos_1] + (len >> ) != A[pos_1 + (len >> )]) ok = ;
if (A[pos_2] + (len >> ) != A[pos_2 + (len >> )]) ok = ;
if (ok) ok = dfs(state >> , len << );
swap(A[pos_1], A[pos_2 + (len >> )]);
return ok;
}
else if (A[pos_2] & (len - ))
{
swap(A[pos_2], A[pos_1 + (len >> )]);
if (A[pos_1] + (len >> ) != A[pos_1 + (len >> )]) ok = ;
if (A[pos_2] + (len >> ) != A[pos_2 + (len >> )]) ok = ;
if (ok) ok = dfs(state >> , len << );
swap(A[pos_2], A[pos_1 + (len >> )]);
return ok;
}
else
{
swap(A[pos_1], A[pos_2]);
if (A[pos_1] + (len >> ) != A[pos_1 + (len >> )]) ok = ;
if (A[pos_2] + (len >> ) != A[pos_2 + (len >> )]) ok = ;
if (ok) ok = dfs(state >> , len << );
swap(A[pos_1], A[pos_2]);
if (ok) return ; ok = ;
swap(A[pos_1 + (len >> )], A[pos_2 + (len >> )]);
if (A[pos_1] + (len >> ) != A[pos_1 + (len >> )]) ok = ;
if (A[pos_2] + (len >> ) != A[pos_2 + (len >> )]) ok = ;
if (ok) ok = dfs(state >> , len << );
swap(A[pos_1 + (len >> )], A[pos_2 + (len >> )]);
return ok;
}
}
} int main()
{
#ifndef ONLINE_JUDGE
freopen("3990.in", "r", stdin);
freopen("3990.out", "w", stdout);
#endif scanf("%d", &n);
Fac[] = ;
for (int i = ; i <= n; i ++)
Fac[i] = Fac[i - ] * i;
for (int i = ; i <= ( << n); i ++)
{
scanf("%d", A + i - );
A[i - ] --;
Cnt[i] = Cnt[i - (i & -i)] + ;
}
for (int s = ; s < ( << n); s ++)
if (dfs(s, )) ans += Fac[Cnt[s]];
printf("%lld\n", ans); #ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
#endif
return ;
}
3990_Gromah