hdu4045(递推)

不会斯特林数的只能用递推思想了，结果发现推出来的就是斯特林数。。。

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <algorithm>

#include <math.h>

#include <map>

#include <queue>

#include <sstream>

#include <iostream>

using namespace std;

#define INF 0x3fffffff

#define N 1010

#define __int64 long long int

#define MOD 1000000007

typedef __int64 LL;

LL dp[N][N];

LL dp1[N][N];

int main()

{

    //freopen("//home//chen//Desktop//ACM//in.text","r",stdin);

    //freopen("//home//chen//Desktop//ACM//out.text","w",stdout);

    int n,r,k,m;

    while(scanf("%d%d%d%d",&n,&r,&k,&m)!=EOF)

    {

        memset(dp,,sizeof(dp));

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

            dp[][i]=i;

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

            for(int j=(i-)*k+;j<=n;j++)

            {

                dp[i][j]=dp[i][j-]+dp[i-][j-k];

                if(dp[i][j]>MOD) dp[i][j]-=MOD;

            }

        LL ans=dp[r][n];

        //if( r < m ) m=r;

        /*

        for(int i=2;i<=m;i++)

        {

            dp[i][0]=1;

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

            {

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

                dp[i][j]=dp[i][j]%MOD;

            }

        }

        //

        for(int i=m+1;i<=r;i++)//固定大小

        {

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

            {

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

                dp[i][j]=dp[i][j]%MOD;

            }

        }*/

        ///////////想的复杂了点，可以优化的！

        memset(dp,,sizeof(dp));

        dp[][]=;

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

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

            {

                dp[i][j]=dp[i-][j]*j+dp[i-][j-]; //分成的堆可以为0 的情况

                dp[i][j]%=MOD;

            }

        LL tmp=;

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

            tmp = (tmp+dp[r][i])%MOD;

        cout<<(tmp*ans)%MOD<<endl;

    }

    return ;

}