排列与交换

wjh15101051's space

卧薪尝胆，厚积薄发。

排列与交换

Date: Wed Aug 29 10:57:10 CST 2018

In Category: NoCategory

Description：

给一个长度为 $n$ 的排列，问：

$1$ 、进行恰好 $K$ 次相邻交换，能得到多少个不同序列。

$2$ 、进行不超过 $K$ 次交换，能得到多少个不同序列。

$1\le n,k \le 3000$

Solution：

第一问：

设 $f[i][j]$ 表示长度为 $i$ 的排列，进行了 $j$ 次交换能得到的不同序列个数。

枚举最后一个数在最终序列中的位置，不难得到 $\begin{align}f[i][j]=\sum_{k=max(k - i + 1)}^jf[i-1][k]\end{align}$ ，这个可以前缀和优化。

第二问：

为了保证补充不漏，和之前某题一样，要求最终每个排列只在用最小次数得到的方案里统计一次。也就是说一个数字最多只会交换一次。

于是这个数可以交换，如果交换那么有 $i-1$ 个位置，也可以不交换，所以转移为 $f[i][j]=f[i-1][j]+(i-1)\times f[i-1][j-1]$ 。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 3010

int f[MAXN][MAXN],s[MAXN][MAXN];

#define MOD 1000000007

void solve1()

{

    memset(f,0,sizeof(f));

    memset(s,0,sizeof(s));

    f[0][0] = 1;

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

    {

        f[i][0] = 1;

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

        {

            if(j - i + 1 <= 0)f[i][j] = s[i - 1][j];

            else f[i][j] = (s[i - 1][j] - s[i - 1][j - i] + MOD) % MOD;

        }

        s[i][0] = f[i][0];

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

        {

            s[i][j] = (s[i][j - 1] + f[i][j]) % MOD;

        }

    }

    for(int i = 2;i <= m;++i)f[n][i] = (f[n][i] + f[n][i - 2]) % MOD;

    cout << f[n][m] << " ";

    return;

}

void solve2()

{

    memset(f,0,sizeof(f));

    f[0][0] = 1;

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

    {

        f[i][0] = 1;

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

        {

            f[i][j] = (f[i - 1][j] + (long long)f[i - 1][j - 1] * (i - 1) % MOD) % MOD;

        }

    }

    int ans = 0;

    for(int i = 0;i <= m;++i)ans = (ans + f[n][i]) % MOD;

    cout << ans << endl;

    return;

}

int main()

{

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

    solve1();

    solve2();

    return 0;

}

In tag: DP-DP DP-前缀和优化DP

wjh15101051