学步园

题目地址 ：　http://acm.bnu.edu.cn/bnuoj/problem_show.php?pid=12886

   由于不擅长DP。对于这题。

  比赛的时候根本没去想。直接pass掉。。。 赛后才发现这题不难。

             
很容易就能推算出不重复的摆法总数是  n! / (n-m)! *（（n-m）^（p-m））

             
然后用记忆化DFS，逐层往前，把重复的剪掉即可。

#include<iostream>
#include<cstring>
#define ll long long

using namespace std;

const int mod=1000000007;
ll c[1300][1300],all[3000],self[3000];

ll cal(int n,int m,int p){
	if(n<=m && m<p) return 0;
	ll res=1;
	for(int i=0;i<p;i++)
		if(i<=m) res=res*(n-i)%mod;
		else res=res*(n-m)%mod;
	return res;
}
void init_(){
	int i,j;
	c[0][0]=1;
	for(i=1;i<=1100;i++){
		c[i][0]=1;
		for(j=1;j<=i;j++)
			c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
	}
}
void init_(int n,int m,int p){
	for(int i=0;i<=n;i++) all[i]=cal(i,m,p);
	memset(self,-1,sizeof(self));
}
ll f(int n,int m,int p){
	if(self[n]!=-1) return self[n];
	self[n]=all[n];
	for(int i=n-1;i>0;i--)
		self[n]=(self[n]-c[n][i]*f(i,m,p))%mod+mod;
	return self[n]%=mod;
}

int main(){
	int  n,m,p;
	ll res;
	init_();
	while(cin>>n>>m>>p){
		init_(n,m,p);
		if(p<n) res=0;
		else res=f(n,m,p);
		cout<<res<<endl;
	}
	return 0;
}