HDU4045_Machine scheduling

题意为要你从编号为1-n的所有机器中间选择出r个机器且每一个机器的编号只差不小于k-1，然后将选择的r个机器分为m组有多少种方案。

其实这题目的两个步骤是相互独立的。

总共的方案数等于选择的方案数乘以分组的方案数。

对于选择的方案数，我们首先选出(r-1)*k+1个数，这样就保证了选择了r个合法的数。

然后我们将剩下的数字填入到这r+1个空中去。这样就相当于是把剩余的那个数字分解为r+1个数字的和有多少种方案。（这里可以dp预处理了）

对于分组的方案数也一样，也是预处理出来的。

对于新加入的一个数，它可以放在前面的任何一个组，也可以独立为一组，这样就可以了。

注意，r个数最多分为r组，所以当m>r的时候，直接m=r即可。

#include <iostream>

#include <cstring>

#include <cstdio>

#define M 1000000007

#define ll long long

#define maxn 1010

using namespace std;

ll P[maxn],f[maxn][maxn],g[maxn][maxn];

ll sum[maxn][maxn];

ll n,m,k,r;

int main()

{

    for (int i=; i<maxn; i++) f[][i]=,sum[][i]=;

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

    {

        for (int j=;j<maxn;j++) sum[i][j]=sum[i-][j];

        f[i][]=,sum[i][]=(sum[i][]+f[i][])%M;

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

        {

              f[i][j]=(f[i][j]+sum[i][j-])%M;

              sum[i][j]=(sum[i][j]+f[i][j])%M;

        }

    }

    g[][]=;

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

    {

        g[i][]=;

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

        {

            g[i][j]=(g[i-][j]*j+g[i-][j-])%M;

        }

    }

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

        for (int j=; j<=i; j++) g[i][j]=(g[i][j-]+g[i][j])%M;

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

    {

        ll tepx=n-(r-)*k-,tepy=r+;

        if (m>r) m=r;

        if (tepx<)

        {

            printf("0\n");

            continue;

        }

        ll ans1=f[tepx][tepy];

        ll ans=;

        ll tep=g[r][m];

        ans=(ans1*tep)%M;

        cout<<ans<<endl;

    }

    return ;

}