仔细审题,我们会发现
小 \(A\) 认为两个操作序列不同,当且仅当操作个数不同,或者至少一个操作不同(种类不同或者操作位置不同)。
所以,对于一种操作,不管是交换哪两段,都算作同一种操作,只会对答案贡献一次。
引理
对于一个合法的操作序列,其中的操作可以互换位置,仍为合法序列。
可以自己手动模拟一下,结论很显然。
那么对于每一次操作,设此次操作的长度为 \(len=2^x\),我们将从头开始每 \(len\) 的长度分为一个块,则有 \(2^{n-x}\) 个块。
对于每一个块,我们要保证他是一个合法的有序序列,又因为 \(2^x\) 是由 \(2^{x-1}\) 的块调整顺序转移而来的,那么对于每个 \(2^{x-1}\) 的块,我们就要找出有多少个两两的块不符合顺序递增。如果有超过两对不合理,则我们可以直接判定此分支下无解,
原因就是对于每种操作,我们只能用一次。
当到边界时且合法时,我们需要加上用到的操作数的阶乘。(原因见引理)
\(AC \kern 0.5emCODE:\)
#include<bits/stdc++.h> #define ri register int #define p(i) ++i using namespace std; namespace IO{ char buf[1<<21],*p1=buf,*p2=buf; inline char gc() {return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;} inline int read() { ri x=0,f=1;char ch=gc(); while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();} while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=gc();} return x*f; } } using IO::read; namespace nanfeng{ static const int N=12; int num[(1<<N)+7],p[N+7],n, ans; inline void Swap(int i,int j,int k) { int len=1<<k,si=(i-1)*len,sj=(j-1)*len; for (ri l(1);l<=len;p(l)) swap(num[si+l],num[sj+l]); } inline int check(int x) {//用于判断交换后的块是否符合要求顺序递增 int len=1<<x; for (ri i(1);i<=(1<<n-x);i+=2) if (num[i*len]+1!=num[i*len+1]) return 0; return 1; } inline void dfs(int x,int cnt) { if (x&&!check(x-1)) return; if (x==n) {ans+=p[cnt];return;} dfs(x+1,cnt); ri ch[5],tot=0,len=1<<x;//一定不要设成全局数组,因为若要定义为全局,向下递归时分支会将他改变,之后回溯时会炸。 for (ri i(1);i<=(1<<n-x);i+=2) { if (num[i*len]+1!=num[i*len+1]) { if (tot==4) return; ch[p(tot)]=i;ch[p(tot)]=i+1; } } if (!tot) return; for (ri i(1);i<=tot;p(i)) { for (ri j(i+1);j<=tot;p(j)) { // if ((i+j==3||i+j==7)&&tot==4) continue; Swap(ch[i],ch[j],x); dfs(x+1,cnt+1); Swap(ch[i],ch[j],x);//记得回溯 } } } inline int main() { // freopen("1.in","r",stdin); n=read(); p[1]=1; for (ri i(2);i<=12;p(i)) p[i]=p[i-1]*i; for (ri i(1);i<=(1<<n);p(i)) num[i]=read(); dfs(0,0); printf("%d\n",ans); return 0; } } int main() {return nanfeng::main();}
目前是洛谷最优解,而且这么写码量也很小。