题目大概意思就是说有n个机器,每天选择r个机器,这任意r个机器编号差不能<k,并且将它们分成不到m个相同的组,一共多少方案?
分两部分做,第一部分是把n个机器选择成r个机器。。但编号差不超过k如何处理?第二部分一看就是裸的斯特灵数。。两部分结果相乘为最后答案。
下面说第一部分,假设每个机器的编号差就是k,这样会出现一个空档,空当数为e=n-(r-1)*k-1,然后把这个空档分配到不同的区域中,r台机器有(r+1)个区域。。。根据插板法
的公式,就是C(e+r+1-1,e),即C(e,r),附代码:
#include <iostream> #define LL __int64 #define mod 1000000007 using namespace std; const int N=1000; LL s[N+5][N+5],c[2*N+5][2*N+5]; void cpre() { c[0][0]=1; int i,j; for (i=1;i<=2*N;i++) for (j=0;j<=i;j++) if (j>(i+1)/2) c[i][j]=c[i][i-j]; else if (j==0) c[i][j]=1; else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod; } void spre() { int i,j; s[0][0]=1; for (i=1;i<=N;i++) for (j=0;j<=i;j++) if (i==j) s[i][j]=1; else if (j==0) s[i][j]=0; else s[i][j]=(j*s[i-1][j]+s[i-1][j-1])%mod; } int main() { int n,r,k,m,i; cpre(); spre(); while (scanf("%d%d%d%d",&n,&r,&k,&m)!=EOF) { LL res,s1=0; int e=n-(r-1)*k-1; if (e<0) { printf("0\n"); continue; } res=c[e+r][r]; for (i=0;i<=m;i++) s1=(s1+s[r][i])%mod; res=(res*s1)%mod; printf("%d\n",res); } return 0; }