有一个长度为n 的排列，现在有一些位置的数已经模糊不清了，你只知道这个排列的逆序对个数是K，你能计算出总共有多少可能的排列吗？
很经典的meet in the middle 不说了，记住有各种精妙实现压复杂度。
#include<cstdio> #include<algorithm> #include<map> #define fo(i,a,b) for(i=a;i<=b;i++) using namespace std; typedef long long ll; const int maxn=1000+10,mx=17297280+5; struct dong{ int x,y; } g[mx]; int L[20000],R[20000],f[1000000+10]; int a[maxn],b[20],c[20][20],d[20],e[20],pl[6000][20],coun[20000]; bool bz[maxn]; int i,j,k,l,r,t,n,m,top,tot,cnt,wdc; ll ans; void pp(int x,int lim){ int i; if (x==lim+1){ ++cnt; fo(i,1,lim) pl[cnt][i]=d[i]; return; } fo(i,1,lim) if (!bz[i]){ bz[i]=1; d[x]=i; pp(x+1,lim); bz[i]=0; } } void dfs(int x,int y,int lim){ if (top-x+1<lim-y) return; int i,j,k,t,s; if (x==top+1){ fo(i,1,cnt){ fo(j,1,lim) e[pl[i][j]]=d[j]; t=0; fo(j,1,lim) t+=c[l+j-1][e[j]]; s=0; fo(j,1,lim){ t+=coun[s>>e[j]]; s+=1<<(e[j]-1); } /*zlt.x=s;zlt.y=t; g[zlt]++;*/ g[++wdc].x=s;g[wdc].y=t; } return; } dfs(x+1,y,lim); if (y<lim){ d[y+1]=x; dfs(x+1,y+1,lim); } } void dg(int x,int y,int lim){ if (top-x+1<lim-y) return; int i,j,k,t,s; if (x==top+1){ int S=0; fo(i,1,lim) S+=1<<(d[i]-1); S^=(1<<top)-1; if (!L[S]) return; fo(i,L[S],R[S]) f[g[i].y]++; fo(i,1,cnt){ fo(j,1,lim) e[pl[i][j]]=d[j]; t=0; fo(j,1,lim) t+=c[l+j-1][e[j]]; s=0; fo(j,1,lim) s+=1<<(e[j]-1); s^=(1<<top)-1; fo(j,1,lim){ t+=coun[s>>e[j]]; s+=1<<(e[j]-1); } /*zlt.x=s;zlt.y=m-t; ans+=(ll)g[zlt];*/ if (m-t<=1000000) ans+=(ll)f[m-t]; } fo(i,L[S],R[S]) f[g[i].y]--; return; } dg(x+1,y,lim); if (y<lim){ d[y+1]=x; dg(x+1,y+1,lim); } } bool cmp(dong a,dong b){ return a.x<b.x; } int main(){ freopen("sequence.in","r",stdin);freopen("sequence.out","w",stdout); scanf("%d%d",&n,&m); fo(i,1,n){ scanf("%d",&a[i]); if (a[i]) bz[a[i]]=1; } fo(i,1,n) if (!bz[i]) b[++top]=i; fo(i,1,n){ if (a[i]) continue; ++tot; fo(j,1,top) fo(k,1,n) if (a[k]){ if (k<i&&a[k]>b[j]) c[tot][j]++; else if (k>i&&a[k]<b[j]) c[tot][j]++; } } fo(i,1,n-1) if (a[i]) fo(j,i+1,n) if (a[j]&&a[i]>a[j]) m--; fo(i,1,top/2) bz[i]=0; pp(1,top/2); fo(i,0,16383){ k=i; while (k){ coun[i]++; k-=(k&-k); } } l=1;r=top/2; dfs(1,0,top/2); sort(g+1,g+wdc+1,cmp); fo(i,1,wdc){ if (g[i].x!=g[i-1].x){ R[g[i-1].x]=i-1; L[g[i].x]=i; } } R[g[wdc].x]=wdc; l=top/2+1;r=top; cnt=0; fo(i,1,top-top/2) bz[i]=0; pp(1,top-top/2); dg(1,0,top-top/2); printf("%lld\n",ans); }