| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 需要注意 |
|---|---|---|---|---|---|
| Inversions problem | ★☆☆☆☆ | 答案正确 | 100 | 2015-02-25 14:34:45 | 无 |
给出全排列，翻转任意[l,r]字符k次，问最终存在多少的数学期望。
| 513G.cpp代码已折叠
展开折叠内容
|
|---|
#include<cstdio>
#include<iostream>
#include<string>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<bitset>
#include<set>
using namespace std;
#define llu unsigned long long
#define lld long long
#define ci const lld&
#define sqr(x) ((x)*(x))
#define dsi(n) lld n;scanf("%lld",&n)
#define si(n) scanf("%lld",&n)
#define f(i,n) for(lld i=1;i<=n;++i)
#define fi(n) f(i,n)
#define f0(i,n) for(lld i=0;i!=n;++i)
#define fd(i,n) for(lld i=n;i>=1;--i)
#define foreach(i,s) for(typeof(s.begin()) i=s.begin();i!=s.end();++i)
#define x first
#define y second
lld n,k,ans=0,ans2;
void dfs(ci t,vector<lld> x)
{
if(t==k)
{
foreach(i,x)
{
for(typeof(x.begin()) j=i;j!=x.end();++j)
{
ans+=(*i>*j);
}
}
ans2++;
return;
}
for(int i=0;i!=n;++i)for(int j=i;j!=n;++j)
{
typeof(x) x2=x;
//foreach(i,x)cout<<*i<<". ";
//cout<<i<<" "<<j<<endl;
reverse(x2.begin()+i,x2.begin()+j+1);
//foreach(i,x2)cout<<*i<<"] ";
//system("pause");
dfs(t+1,x2);
}
}
int main()
{
si(n);
si(k);
vector<lld> p;
fi(n)
{
dsi(a);
p.push_back(a);
}
dfs(0,p);
cout<<setprecision(16)<<double(ans)/ans2;
}
|
CloudLunar