[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 ;

 }

巴特西

[hdu5225][BC#40]Tom and permutation

最新文章

热门文章