hdu4045(递推)

桃扇骨 2022-03-28 07:50 236阅读 0赞

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

#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,0,sizeof(dp));
            for(int i=1;i<=n;i++)
                dp[1][i]=i;
            for(int i=2;i<=r;i++)
                for(int j=(i-1)*k+1;j<=n;j++)
                {
                    dp[i][j]=dp[i][j-1]+dp[i-1][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,0,sizeof(dp));
            dp[1][1]=1;
            for(int i=2;i<=r;i++)
                for(int j=1;j<=m;j++)
                {
                    dp[i][j]=dp[i-1][j]*j+dp[i-1][j-1]; //分成的堆可以为0 的情况
                    dp[i][j]%=MOD;
                }
    
            LL tmp=0;
            for(int i=1;i<=m;i++)
                tmp = (tmp+dp[r][i])%MOD;
            cout<<(tmp*ans)%MOD<<endl;
        }
        return 0;
    }