#include <iostream> #include <vector> #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; } } //将1~n全排列，放入二维数组perm void creatperm(vector<vector<int> > &perm) { vector<int> temp;//1~n的临时vector for(int i=1;i<=n;i++) temp.push_back(i); do{ perm.push_back(temp); }while(next_permutation(temp.begin(), temp.end())); } //过滤，刷掉返回false，如果没有刷掉返回true bool chooseperm(const vector<int> &permtemp) { for(int i=0;i<n;i++) { if(a[i]) { if(a[i]!=permtemp[i]) return false; } } return true; } //计算cnt 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); } //第一步 //先将1～n全排列（permutation），生成一个二维数组备用（每一行代表一种排序方式）； vector<vector<int> > perm;//用于存放全排列的二维vector creatperm(perm); cout<<"全排列:"<<endl; printperm(perm);//测试生成是否正确 //第二步 //过滤该二维数组，选取满足特定位置上为输入序列中非0数的序列，生成新的二维数组； vector<vector<int> > choose;//过滤之后的二维数组 for(int i=0;i<perm.size();i++) { if(chooseperm(perm[i])) choose.push_back(perm[i]); } cout<<"过滤后:"<<endl; printperm(choose);//测试生成是否正确 //第三步 //逐行验证其有序对是否为k，统计符合的个数； count(choose); cout<<"符合的排列个数"<<endl; cout<<cnt<<endl; }