Permutation Counting HDU3664 UVALive - 5092 DP

传送门：HDU3664

题意：问1-n的全排列中，满足ai>i（1<=i<=n）的数有k个的序列有几个。

思路：假设已知n-1的全排列中所有k的情况，那么先把n放到序列最后，然后考虑交换，若n与任意一个满足ai>i的数交换，则不会改变该序列的k值，若与ai<=i的数交换，则会使该序列k值加一。

因此很容易求得状态转移方程：dp[i][j]=dp[i-1][j]*(j+1)+dp[i-1][j-1]*(i-j); 

dp[x][y]表示1-x的全排列中满足ai>i（1<=i<=x）的数为y的序列个数。

当然此题也可以打表找规律，用个next_permutation函数打表还是不难写的，规律也不是很难发现。

代码：

#include<bits/stdc++.h>
#define ll long long
#define pi acos(-1)
#define inf 0x3f3f3f3f
#define mod 1000000007
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define rep(i,x,n) for(int i=x;i<n;i++)
#define per(i,n,x) for(int i=n;i>=x;i--)
using namespace std;
typedef pair<int,int>P;
const int MAXN=100010;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
ll dp[1010][1010];
int main()
{
	int n,k;
	std::ios::sync_with_stdio(0);
	while(cin>>n>>k)
	{
		dp[1][0]=1;
		for(ll i=1;i<=n;i++)
		{
			dp[i][0]=1;
			for(ll j=1;j<i;j++)
			dp[i][j]=(dp[i-1][j]*(j+1)+dp[i-1][j-1]*(i-j))%mod;
		}
		cout<<dp[n][k]<<endl;
	}
 	return 0;
}