Machine scheduling

Time Limit: 5000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1000    Accepted Submission(s): 363

5 2 3 2

6

Hint

Sample input means you can choose 1 and 4,1 and 5,2 and 5 in the same day.

And you can make the machines in the same group or in the different group.

So you got 6 schemes.

1 and 4 in same group,1 and 4 in different groups.

1 and 5 in same group,1 and 5 in different groups.

2 and 5 in same group,2 and 5 in different groups.

We assume 1 in a group and 4 in b group is the same as 1 in b group and 4 in a group.

解题思路：

这题考的是排列组合

（1）首先，要从n个元素编号1~n中选出r个元素来，使得任意两个元素编号相差>=k

解法：先按照 1 k+1 2*k+1 .... (r-1)*k+1 也就是刚好 间隔 k个排列下来

那么 总共n个元素，剩余 n-(r-1)*k-1个元素可以看成空格，极为space,将它们插入这r个元素的r+1个空档中，

这样就能保证枚举了素有的方法数，切满足任意两个元素编号相差>=k的要求

所以这个问题简化为：将space个元素分配到r+1个区域中，可以为空

答案为：stir2[space][r+1],第二类斯特林数

（2）然后，再将选取的r个元素分为不超过g组，枚举想要的组数即可

只需要枚举对应的组数， 1~min(r,g)

转化问题：将n个元素最多分为m个集合，不为空的方案法,插板法，答案为：c[n+m-1][m-1]

解题代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

typedef long long ll;

const ll mod=1000000007;

const int maxn=1010;

int n,r,m,g;

ll c[2*maxn][2*maxn],stir2[maxn][maxn];

void ini(){

    for(int i=1;i<2*maxn;i++){

        c[i][0]=c[i][i]=1;

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

            c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;

    }

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

        stir2[i][0]=0;

        stir2[i][i]=1;

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

            stir2[i][j]=((ll)j*stir2[i-1][j]+stir2[i-1][j-1])%mod;

    }

}

ll get1(ll n,ll m){//将n个元素最多分为m个集合，不为空的方案法。

    return c[n+m-1][m-1];

}

ll get2(ll n,ll m){//将n个元素分配到m个区域中，可以为空。

    return stir2[n][m];

}

void solve(){

    int space=n-(r-1)*m-1;

    if(space<0){

        printf("0\n");

        return ;

    }

    ll ans=0;

    //将r个元素分为i组

    for(int i=1;i<=min(r,g);i++){

        ans=(ans+get2(r,i))%mod;

    }

    ans=( ans*get1(space,r+1) )%mod;

    cout<<ans<<endl;

}

int main(){

    ini();

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

        solve();

    }

    return 0;

}