再贴一种方法哈，昨天吃饭时候跟朋友讨论，换了一种思路，昨天晚上做了一下。

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <unordered_map>
#include <map>
#include <algorithm>
using namespace std;

//输入参数
int n;//输入n个数
int k;//有序对k对
vector<int> a;//输入序列a，包含1~n的n个数，有若干个数（不超过10个）是0
//输出参数
int cnt=0;//合法排列的数目

//输出perm数组，用于测试
void printperm(const vector<vector<int> > &perm)
{
    for(int i=0;i<perm.size();i++)
    {
        for(int j=0;j<perm[0].size();j++)
            cout<<perm[i][j]<<" ";
        cout<<endl;
    }
}

//第一步，选出用于全排列的数
void chooseperm(vector<int> &permuse)
{
    vector<int> permtemp;
    int permnum=0;//需要全排列的数的个数
    int temp=0;
    for(int i=1;i<=n;i++)//初始化为1~n
        permtemp.push_back(i);
    for(int i=0;i<a.size();i++)//移除输入中已有的数
    {
        if(a[i])
        {
            remove(permtemp.begin(),permtemp.end(),a[i]);
            temp++;
        }
    }
    permnum=n-temp;//n-移除的数，即需要全排列的数的个数
    for(int i=0;i<permnum;i++)//得到用于全排列的vector
        permuse.push_back(permtemp[i]);
}

//第二步，对第一步选出的数全排列
void creatperm(vector<vector<int> > &perm,vector<int> &permuse)
{
    do{
        perm.push_back(permuse);
    }while(next_permutation(permuse.begin(), permuse.end()));
}

//第三步，拼接第二步得到的全排列的二维vector和已有的输入
void insertperm(vector<vector<int> > &perminsert,const vector<vector<int> > &perm)
{
    for(int i=0;i<perm.size();i++)
    {
        vector<int> tempinsert;
        int q=0;
        for(int p=0;p<n;p++)
        {
            if(a[p])
                tempinsert.push_back(a[p]);
            else
                tempinsert.push_back(perm[i][q++]);
        }
        perminsert.push_back(tempinsert);
    }
    
}

//第四步，逐行验证其有序对是否为k，统计符合的个数
void count( const vector<vector<int> > &choose)
{
    for(int i=0;i<choose.size();i++)
    {
        int ktemp=0;
        vector<int> temp=choose[i];
        for(int j=0;j<temp.size();j++)
        {
            for(int jj=j+1;jj<temp.size();jj++)
            {
                if(temp[j]<temp[jj])
                    ktemp++;
            }
        }
        if(ktemp==k)
            cnt++;
    }
}

int main(){
    //输入
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        int temp;
        cin>>temp;
        a.push_back(temp);
    }
    
    //第一步，选出用于全排列的数
    vector<int> permuse;//用于全排列的数
    chooseperm(permuse);
    cout<<"用于全排列的数"<<endl;
    for(int i=0;i<permuse.size();i++)
        cout<<permuse[i]<<" ";
    cout<<endl;
    
    //第二步，对第一步选出的数全排列
    vector<vector<int> > perm;//得到全排列的二维vector
    creatperm(perm,permuse);
    cout<<"全排列"<<endl;
    printperm(perm);
    
    //第三步，拼接第二步得到的全排列的二维vector和已有的输入
    vector<vector<int> > perminsert;
    insertperm(perminsert,perm);
    cout<<"符合模板的排列"<<endl;
    printperm(perminsert);
    
    //第四步，逐行验证其有序对是否为k，统计符合的个数
    count(perminsert);
    cout<<"符合的排列个数"<<endl;
    cout<<cnt<<endl;
}