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;
}