51Nod 1250 排列与交换 —

题目：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1250

看了半天...

把第一问想成逆序对的话似乎很容易想了，新加入一个数，可以往前挪动，增加的逆序对数就是它后面那些数的个数；

所以 f[i][j] = ∑(k = max( 0 , j - i + 1)) f[i-1][k]，用前缀和即可；

第二问正好用第一类斯特林数；

第一类斯特林数 str[i][j] 表示把 i 个数分成 j 个环，环有顺序的方案数，str[i][j] = str[i-1][j-1] (自成一环) + ( i - 1 ) * str[i-1][j] (跟到某个后面)

对应到这道题，原来每个数自己是一个环，表示它就在自己的位置上；

一个有顺序的环，按一个顺序往过数，一个数到下一个数相互交换，就对应了一种交换；

str[i][j] 中，i - j 个数与别的环合并，也就是发生了一次交换，所以答案就是 ∑(n - k <= i <= n ) str[n][i]

注意不要 MLE ...

用滚动数组求斯特林数得注意一点，初值 str[0][0] 不要赋成1，然后后面 i == j 时也求出来即可，感性理解一下的话~

这题...好像也不难啊。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int const maxn=,mod=;

int n,m;

ll f[][maxn],s[][maxn],str[][maxn],ans1,ans2;

void init()

{

//    for(int i=0;i<=1;i++)str[i][i]=1;

    str[][]=;//滚动数组！让初始化符合意义

    for(int i=;i<=n;i++)

        for(int j=;j<=i;j++)//因为滚动所以 str[i][i]也在这里求

        {

            int p=(i&),q=!p;

            str[p][j]=(str[q][j-]+(i-)*str[q][j]%mod)%mod;

        }

}

int main()

{

    scanf("%d%d",&n,&m);

    init();

    for(int i=;i<=;i++)

    {

        f[i][]=,s[i][]=;

        for(int j=;j<=m;j++)s[i][j]+=s[i][j-];

    }

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++)

        {

            int p=(i&),q=!p;

            if(j-i+<=)f[p][j]=s[q][j];

            else f[p][j]=(s[q][j]-s[q][j-i]+mod)%mod;

            if(j)s[p][j]=(s[p][j-]+f[p][j])%mod;

            else s[p][j]=f[p][j];

        }

    int tmp=m;

    while(tmp>=)ans1=(ans1+f[n&][tmp])%mod,tmp-=;

    for(int i=n-m;i<=n;i++)ans2=(ans2+str[n&][i])%mod;

    printf("%lld %lld\n",ans1,ans2);

    return ;

}

巴特西

51Nod 1250 排列与交换 —— DP

最新文章

热门文章