设x1,x2,x3...,xn是集合{1，2，3，...，n}的一个排列，排列中逆序对的对数称为逆序数，（如1432的逆序数为3，即有3对逆序对，分别为：43，42，32）。则当x3=4时（即第3个数为4），所有排列的逆序数的和为多少？（n=6时，为2020年全国高中数学联赛浙江赛区初赛试题填空第10题）
输入格式:
输入一个n(n<10)。
输出格式:
输出逆序数的和。
输入样例:
6
输出样例:
912
作者严华云单位湖州师范学院代码长度限制16 KB时间限制400 ms内存限制64 MB#include<stdio.h>
#include<iostream>
using namespace std;
int n,num[100];
int visit[100]={0};
int sum=0;
void pailie(int t){
int i,j;
if(t>n){
if(num[3]!=4){
return;
}
for(j=1;j<n;j++){
for(int k=j+1;k<=n;k++){
// cout<<num[j]<<num[k]<<endl;
if(num[k]<num[j]){
// sum+=(num[j]*10+num[k]);
sum++;
}
}
//cout<<num[j]<<" ";
}
//cout<<endl;
}
else{
for(i=1;i<=n;i++){
if(visit[i]==0){
num[t]=i;
visit[i]=1;
pailie(t+1);
visit[i]=0;
}
}
}
}
int main(){
cin>>n;
pailie(1);
cout<<sum;
}
设x1,x2,x3...,xn是集合{1，2，3，...，n}的一个排列，排列中逆序对的对数称为逆序数，（如1432的逆序数为3，即有3对逆序对，分别为：43，42，32）。则当x3=4时（即第3个数为4），所有排列的逆序数的和为多少？（n=6时，为2020年全国高中数学联赛浙江赛区初赛试题填空第10题）
输入格式:
输入一个n(n<10)。
输出格式:
输出逆序数的和。
输入样例:
6
输出样例:
912
作者
严华云
单位
湖州师范学院
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
#include<stdio.h>
#include<iostream>
using namespace std;
int n,num[100];
int visit[100]={0};
int sum=0;
void pailie(int t){
int i,j;
if(t>n){
if(num[3]!=4){
return;
}
for(j=1;j<n;j++){
for(int k=j+1;k<=n;k++){
// cout<<num[j]<<num[k]<<endl;
if(num[k]<num[j]){
// sum+=(num[j]*10+num[k]);
sum++;
}
}
//cout<<num[j]<<" ";
}
//cout<<endl;
}
else{
for(i=1;i<=n;i++){
if(visit[i]==0){
num[t]=i;
visit[i]=1;
pailie(t+1);
visit[i]=0;
}
}
}
}
int main(){
cin>>n;
pailie(1);
cout<<sum;
}