[hdu5225][BC#40]Tom and permutation

  好久没写题解了。。GDKOI被数位DP教做人了一发,现在终于来填数位DP的大坑了>_<。

  发现自己以前写的关于数位DP的东西...因为没结合图形+语文水平拙计现在已经完全看不懂了嗯。

  看来看去感觉还是这篇关于数位DP的介绍靠谱:http://wenku.baidu.com/view/d2414ffe04a1b0717fd5dda8.html

  想题的时候结合图形食用效果更佳。

  题意是说,对于一个给定的n的排列,要求出 (所有字典序<给定排列的排列)的逆序对个数和。

  预处理出f[i]表示i的所有排列中,逆序对的个数。(事实上也是i个数的所有排列中逆序对的个数)

  然后像那篇论文里面的姿势处理就好了。

  每次把逆序对分为三种:已确定的数和后面的数之间的逆序对、已确定的数之间的逆序对,后面的数之间的逆序对。

  前两种可以放到一起统计(和后面的数的具体顺序无关),第三种就是预处理出来的东西。

  顺便在hdu上压了发代码最短= =(空间实在无力>_<

 #include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const ll modd=;
ll f[],a[];//a数组存阶乘的值
ll i,j;
int n,x;
bool u[];
inline ll run(){
ll ans=,now=,mn;
memset(u,,n+);
for(i=;i<=n;i++){
scanf("%d",&x);u[x]=;
for(j=,mn=;j<x;j++)
if(!u[j])ans+=f[n-i]+a[n-i]*(now+mn),ans%=modd,mn++;
for(j=;j<x;j++)if(!u[j])now++;
}
return ans;
}
int main(){
a[]=;f[]=;
for(i=;i<=;i++){
a[i]=a[i-]*i%modd;
f[i]=(i*f[i-]+a[i-]*(i-)*i/)%modd;
}
while(scanf("%d",&n)==)printf("%lld\n",run());
return ;
}
上一篇:oracle存储过程获取异常信息码和异常信息


下一篇:Oracle存储过程中异步调用的实际操作步骤