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