HDU 4045 Machine scheduling 题解：组合数+斯特林数

This blog post is only available in Simplified Chinse.

HDU 4045 Machine scheduling：题目链接

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

Problem Description

A Baidu’s engineer needs to analyze and process large amount of data on machines every day. The machines are labeled from 1 to n. On each day, the engineer chooses r machines to process data. He allocates the r machines to no more than m groups ,and if the difference of 2 machines' labels are less than k,they can not work in the same day. Otherwise the two machines will not work properly. That is to say, the machines labeled with 1 and k+1 can work in the same day while those labeled with 1 and k should not work in the same day. Due to some unknown reasons, the engineer should not choose the allocation scheme the same as that on some previous day. otherwise all the machines need to be initialized again. As you know, the initialization will take a long time and a lot of efforts. Can you tell the engineer the maximum days that he can use these machines continuously without re-initialization.

Input

Input end with EOF. Input will be four integers n,r,k,m.We assume that they are all between 1 and 1000.

Output

Output the maxmium days modulo 1000000007.

Sample Input

5 2 3 2

Sample Output

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.

Translation

有 n 台机器，你要选择其中的 r 台处理数据，使得其中相邻两台下标的距离不小于 k，并且需要你把选出的 k 台分成不超过 m 组。问你有多少种方案。

Solution

分解问题，先选出相邻两台下标距离均不小于 k 的 r 台机器，然后再考虑分成不超过 m 组。

对于第二问，裸的第二类斯特林数。

接下来考虑第一问。假设我们从第一台机器开始每隔 k-1 台机器就选一台，选到最后（ r 台）会发现还剩余一些位置。我们可以考虑把这些位置插入前面的 r+1 个空隙里。显然最后剩余的位置是： $n-((r-1)\ast k+1)$ 。接下来我们就是要把 $n-((r-1)\ast k+1)$ 个元素分成 $r+1$ 个集合，集合可以为空。放球问题的一种：球不同，盒相同，可以为空。做法是：把盒子为空转换成盒子不能为空的做法，让每个盒子里都要有球，则要多放 $r+1$ 个球。现在我们就解决球不同、盒相同、不能为空的放球问题，显然可以用隔板法来做，最后答案：

C_{n-((r-1)]\ast k+1+r+1-1)}^{r} \ast \sum_{i=1}^{min(r,m)}S(r,i)

Code

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=1005,tt=1e9+7;
int n,r,k,m,c[maxn*2][maxn*2],s[maxn][maxn],lst[maxn];
inline void Build(){
    for (int i=0;i<=1000;i++) s[i][i]=1;
    for (int i=1;i<=1000;i++)
        for (int j=1;j<i;j++)
            s[i][j]=(s[i-1][j-1]+(long long)s[i-1][j]*j%tt)%tt;
    c[0][0]=1;
    for (int i=1;i<=1000;i++){
        c[i][0]=c[i][i]=1;
        for (int j=1;j<i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%tt;
    }
}
inline int C(int x,int y){
    return c[x][y];
}
int main(){
    Build();
    while (scanf("%d%d%d%d",&n,&r,&k,&m)!=-1){
        if (n-((r-1)*k+1)+r<0) {printf("0\n");continue;}
        int sum=0;
        for (int i=1;i<=min(r,m);i++) sum=(sum+s[r][i])%tt;
        printf("%d\n",(long long)C(n-((r-1)*k+1)+r,r)*sum%tt);
    }
    return 0;
}

7/29/2018