前言
卧槽，距我上次更新博客已经整整1年了…
关于本人之前一直沉迷whk与fgo，久久未动OI和博客，眼看即将NOIP2021，所以我重新开始写博客记录一下我的康复训练之旅。
题目
题面描述
有一个$1∼n$的排列，其中有$m$个位置上的数缺失了。
已知这个排列的逆序对数恰好为$k$，求有多少种可能的排列。
输入格式
第一行两个正整数$n,k$。
接下来一行$n$个正整数$a_1∼n$，若$a_i=0$则表示这个位置上的数缺失了。
输出格式
共一行，一个整数表示答案。
样例一
input
5 5
4 0 0 2 0output
2数据范围与约定
Subtask1(20%)：$m≤10$
Subtask2(20%)：$n≤100$
Subtask3(30%)：0出现的位置为连续一段
Subtask4(30%)：无特殊限制
对于100%的数据，$1≤n≤10^5$,$0≤m≤14$,$0≤k≤10^9$
题解
打比赛的时候也就会搓个Subtask2和3，但观察一下m的范围不难发现其实挺sb的，如果meet in middle的话，那复杂度就是$O(C_{14}^{7}*7!)$差不多一千多万的样子，如果写的劣一点可能还带个log。但我们先不说这个，先说做法——首先我们算出除了不确定的数外所有的数的逆序对数，然后我们预处理$cnt[i][j]$表示在第$i$个空位放置第$j$个未出现的数的逆序对数贡献(注意我们未出现的数在数组中为递增的,这点对后面优化计数有帮助)。接下来我们把$m$个空位分成$m/2$，$m-(m/2)$大小的两个部分，并且dfs枚举出这两部分有哪些数(不考虑顺序)，在把一个数加入左或者右部分时统计左右部分跨区产生逆序对个数，因为是从小到大放数，所以每次向左边加数时加上右边大小即可。然后考虑区内贡献，首先是考虑放入数的顺序对于非空位贡献，这部分通过$cnt$数组可轻松计算，然后考虑区内贡献，因为我们从小到大加入点，我们考虑开个$res$计算在$i$这个数放入前$1 ∼ i$内有多少数未被放入，那么这$res$个数必然放入i后，产生$res$的贡献，由此我们可以把树状数组的$log$统计变为$O(1)$统计，至于答案对于左边开个桶记录，右边加对应符合条件的桶的贡献就可以了。
代码
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define Maxn 100005
#define Maxm 20
#define gc getchar
#define W while
#define isd isdigit
#define LL long long
#define lowbit(x) (x&(-x))
#define F(i,x,y) for (LL i=x;i<=y;i++)
#define D(i,x,y) for (LL i=x;i>=y;i--)
using namespace std;
struct FastIO{
static const LL S=1048576;
char buf[S],*L,*R;LL stk[20],Top;
~FastIO(){clear();}
inline char nc(){return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;}
inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
inline void pc(char ch){Top==S&&(clear(),0);buf[Top++]=ch;}
inline void endl(){pc('\n');}
FastIO& operator >> (LL& ret){ret=0;LL f=1;char ch=nc();while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}ret*=f;return *this;}
FastIO& operator >> (char* s){register LL Len=0;register char ch=nc();while(ch!='\n'){*(s+Len)=ch;Len++;ch=nc();}}
FastIO& operator << (LL x){if(x<0){pc('-');x=-x;}do{stk[++stk[0]]=x%10;x/=10;}while(x);while(stk[0]) pc('0'+stk[stk[0]--]);return *this;}
FastIO& operator << (char ch){pc(ch);return *this;}
FastIO& operator << (string str){register LL Len=str.size()-1;for(stk[0]=0;Len>=0;Len--) stk[++stk[0]]=str[Len];while(stk[0]) pc(stk[stk[0]--]);return *this;}
}fin,fout;
LL k,n,a[Maxn],T[Maxn],top=0,tot=0,tree[Maxn],cnt[Maxm][Maxm],K=0,L[Maxm],R[Maxm],C[Maxn*14],P[Maxn*14],TOT=0;bool vis[Maxn],flagL[Maxm],flagR[Maxm];
LL ans=0;
inline void add(LL i,LL x){W(i<=n)tree[i]+=x,i+=lowbit(i);}
inline LL ask(LL i){LL res=0;W(i)res+=tree[i],i-=lowbit(i);return res;}
inline void dfsL(LL now,LL sum,LL limit)
{
if (now>limit){C[sum]++;P[++TOT]=sum;return;}LL res=0;
F(i,1,limit)
{
if (flagL[i]) continue;
flagL[i]=1;
dfsL(now+1,sum+cnt[now][L[i]]+res,limit);
flagL[i]=0;res++;
}
}
inline void dfsR(LL now,LL sum,LL O,LL limit,LL limit2)
{
if (now>limit){if (O>=sum) ans+=C[O-sum];return;}LL res=0;
F(i,1,limit)
{
if (flagR[i]) continue;
flagR[i]=1;
dfsR(now+1,sum+cnt[limit2+now][R[i]]+res,O,limit,limit2);
flagR[i]=0;res++;
}
}
inline void dfs(LL now,LL topL,LL topR,LL T)
{
// cout<<now<<" "<<topL<<" "<<topR<<" "<<T<<" "<<top/2<<" "<<top-(top/2)<<endl;
if (now>top)
{
F(i,1,TOT) C[P[i]]=0;
TOT=0;
topL--,topR--;
// F(i,1,topL) cout<<L[i]<<" ";
// cout<<endl;
// F(i,1,topR) cout<<R[i]<<" ";
// cout<<endl;
// cout<<"T="<<T<<endl;
if (T>k) return;
dfsL(1,0,topL);
dfsR(1,0,k-T,topR,topL);return;
}
if (topL<=top/2) L[topL]=now,dfs(now+1,topL+1,topR,T+topR-1),L[topL]=0;
if (topR<=top-(top/2)) R[topR]=now,dfs(now+1,topL,topR+1,T),R[topR]=0;
}
int main()
{
// freopen("s.in","r",stdin);
// freopen("s.out","w",stdout);
fin>>n>>k;
F(i,1,n) fin>>a[i],vis[a[i]]=1;F(i,1,n) if (!vis[i]) T[++top]=i;
F(i,1,n) if (a[i]) add(a[i],1),tot+=ask(n)-ask(a[i]);else{K++;F(j,1,top) cnt[K][j]=ask(n)-ask(T[j]);}
F(i,1,n) if (a[i]) add(a[i],-1);D(i,n,1) if (a[i]) add(a[i],1);else{F(j,1,top) cnt[K][j]+=ask(T[j]-1);K--;}D(i,n,1) if (a[i]) add(a[i],-1);
k-=tot;if (k>Maxn*14){return puts("0"),0;}if (k>=0) dfs(1,1,1,0);fout<<ans<<'\n';return 0;
}
/*
9 4
1 2 3 0 4 5 6 0 0
5 5
4 0 0 2 0
*/