hdu3664 Permutation Counting（dp）

hdu3664 Permutation Counting

题目传送门

题意：

在一个序列中，如果有k个数满足a[i]>i；那么这个序列的E值为k，问你

在n的全排列中，有多少个排列是恰好是E值为k的序列？

思路：

定义dp[i][j]: 在 i 的全排列中，E值为j的个数；则从i转移到i+1时，有三种情况：

1）把i+1加到最后，E值不变；

2）把i+1与那些已经满足a[i]>i的数交换，E值不变；

3）把i+1与那些不满足a[i]>i的数交换，E值加一。

根据上面得到的转移方程为：

dp[i][j]=(dp[i-1][j]+dp[i-1][j]*j+dp[i-1][j-1]*(i-j))%mod;

代码：

#include<iostream>

#include<string.h>

#include<algorithm>

#include<stdio.h>

#include<math.h>

#include<queue>

#include<stack>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef long long ll;

typedef pair<int,int> PII;

#define mod 1000000007

#define pb push_back

#define mk make_pair

#define all(x) (x).begin(),(x).end()

#define fi first

#define se second

//head

#define N 1001

ll dp[N][N];

int n,k;

int main()

{

     for(int i=;i<=;i++)//注意这里的i只能到1000，不然会超时

        {

            dp[i][]=;

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

            {

                dp[i][j]=(dp[i-][j]+dp[i-][j]*j+dp[i-][j-]*(i-j))%mod;

            }

        }

    while(~scanf("%d %d",&n,&k))

    {

        printf("%lld\n",dp[n][k]);

    }

    return ;

}

巴特西

hdu3664 Permutation Counting（dp）

最新文章

热门文章