Hdu 4045 Machine scheduling (组合数，斯特林数)

不念不忘少年蓝@ 2022-09-17 11:14 173阅读 0赞

11年北京网络赛的题目

题意：有N个机器，每天选出R个机器，而且每两个机器的编号差要大于等于K，每天将这R个机器最多分为M组工作，问最多有多少种方案。

思路：问题由两部分构成：第一，从N个机器中选出R个满足条件的机器的方案数；第二，将R个机器最多分为M组有的方案数。二者乘积即为答案。

第一部分：

先满足每两个机器之间至少有K-1个间隔，也就是还剩下rem=n-((r-1)\*k+1)个机器可以随意安排，把这些多余的插入到R个机器之间(加上两端共R+1个位置)。问题也就变为rem个相同的球分到R+1个不同的组可以为空这种模型，不难推出是C(rem+R，R)，网上有说直接用插板法公式。可参考：[插板法][Link 1]

第二部分：R个元素分为i个非空集合是第二类斯特林数，对i为1至m求和即可。

#include <cstdio>
    #define min(a,b) ((a)<(b)?(a):(b))
    
    const int mod = 1000000007;
    const int N = 1005;
    
    int C[2*N][2*N];
    __int64 stir2[N][N];
    
    void Init ()
    {
    	int i,j;
    	for (i=1;i<=2000;i++)
    	{
    		C[i][0]=C[i][i]=1;
    		for (j=1;j<i;j++)
    			C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    	}
    	for (i=1;i<=1000;i++)
    	{
    	    stir2[i][0]=0;
    	    stir2[i][i]=1;
    	    for (j=1;j<i;j++) // <= WA
                stir2[i][j]=(stir2[i-1][j-1]+j*stir2[i-1][j])%mod;
        }
    
    }
    
    int main ()
    {
    	Init ();
    	int n,m,k,r;
    	while (~scanf("%d%d%d%d",&n,&r,&k,&m))
    	{
    	    int rem=n-((r-1)*k+1);
    	    if (rem<0)  //无法满足分割要求
    	    {
    	        printf("0\n");
    	        continue;
    	    }
    	    __int64 sum=0,ans=C[rem+r][r];
    	    for (int i=1;i<=m;i++)
                sum=(sum+stir2[r][i])%mod;
            ans=(ans*sum)%mod;
            printf("%I64d\n",ans);
    	}
    	return 0;
    }

[Link 1]: http://zhidao.baidu.com/link?url=W7jIx7OImBhEH-D-46RB4csRpYe2PLNAo66OAKcUnzTwvevPmFXZmawiGZE_NEZXQhwzj4g5wi7ObjVW266UmK