D - Maximum Value Problem FZU - 2037

題意；

這個序列[1，3，2，4]，maxx=0.如果將maxx賦值為最大值需要3次，第一次為maxx=1，第二次maxx=3，第三次maxx=4
給你一個n，求n全排列的查找次數(shù)之和，以及次數(shù)/全排列數(shù)量

題解：

推公式，，，我也不知道怎么推的
貌似打表可以得到：
f[n]表示n的全排列的查找次數(shù)之和
f(n) = f(n - 1) * n + (n - 1)!
p[n]=f[n]/n! = p[n-1]+1/n

代碼：

#include<bits/stdc++.h> #define debug(a,b) printf("%s = %d\n",a,b) typedef long long ll; using namespace std;inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=1e6+9; const int mod=1e9+7; int f[maxn]; double p[maxn]; void init(){f[1]=1;f[2]=3;p[2]=1.5;ll cal=2;for(int i=3;i<=1e6+2;i++){f[i]=(f[i-1]*i+cal)%mod;p[i]=p[i-1]+1.0/i; cal*=i;} } int main() {int t;init(); cin>>t;int cas=0;while(t--){int n;cin>>n;printf("Case %d: %lld %.6lf\n", ++cas, f[n], p[n]);} }

總結(jié)

以上是生活随笔為你收集整理的D - Maximum Value Problem FZU - 2037的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。