2011ACM北京网络预选赛 F Machine scheduling (BUPT 216)

2011ACM北京网络预选赛 F Machine scheduling (BUPT 216)



这题比赛时候过得很纠结……最后还是学长过的……比赛时候脑子可能不够清楚，一直WA……
首先，这个题要分成两个部分解决：
第一部分：从n个东西里面取出r个，每个间距至少为 k （1～K不行，1～K ＋ 1行）
第二部分：将这r个东西分成至多m组，可以有空组
第二部分貌似好久之前搞OI的时候干过……贴过来：

    
        
            
             N球放在M个盒子里，求共有多少种放法
            
             但是有3个不同的条件 ：N个球是否相同，M个盒子是否相同，是否允许有盒子空着
            
            
                
                    
                        
                         球和球
                        
                        
                         盒和盒
                        
                        
                         空盒
                        
                        
                         情况数
                        
                    
                    
                        
                         有区别
                        
                        
                         有区别
                        
                        
                         有空盒
                        
                        
                         mn
                        
                    
                    
                        
                         有区别
                        
                        
                         有区别
                        
                        
                         无空盒
                        
                        
                         M！s（n,m）
                        
                    
                    
                        
                         有区别
                        
                        
                         无区别
                        
                        
                         有空盒
                        
                        
                         S(n,1)+s(n,2)+…+s(n,m),n>=m
                         S(n,1)+s(n,2)+&#8230;+s(n,n),n<=m
                        
                    
                    
                        
                         有区别
                        
                        
                         无区别
                        
                        
                         无空盒
                        
                        
                         S(n,m)
                        
                    
                    
                        
                         无区别
                        
                        
                         有区别
                        
                        
                         有空盒
                        
                        
                         C(n+m-1,n)
                        
                    
                    
                        
                         无区别
                        
                        
                         有区别
                        
                        
                         无空盒
                        
                        
                         C(n-1,m-1)
                        
                    
                    
                        
                         无区别
                        
                        
                         无区别
                        
                        
                         有空盒
                        
                        
                         F(m,n)
                        
                    
                    
                        
                         无区别
                        
                        
                         无区别
                        
                        
                         无空盒
                        
                        
                         F(m,n-m)
                        
                    
                
            
            
            
            
        
    

然后，其中的F(m,n)貌似是当时写过的一个DP，S(M,N)是第二类stirling数&#8230;&#8230;递推公式：1 int S(int n,int m) {2     if (n == m || m == 1) return 1;3     return m * S(n - 1, m) + S(n - 1, m - 1);4 }第一部分：可以看作这么一个生成函数的相关问题：由于每个东西之间都隔了>=K－1的一段距离，因此一个可行解可以看作，长度为K，K + 1，K + 2的棍子r － 1个（我们认为每个棍子的头是我们取的点），拼接成长度为Len的一个大段，之后再堵上一个，就是一个Len ＋１的可行解&#8230;&#8230;而r - 1根棍子，拼成长度为Len 的可行解数目，就是(X^K + X^(K + 1) + X^(K + 2) + .....) ^ (r - 1)，这个多项式，展开之后，X^Len项前面的系数&#8230;&#8230;不过&#8230;&#8230;由于数据范围，直接搞是不成的&#8230;&#8230;于是提取，变形：X^(K * (r - 1))  * (1 + X + X^2 + X ^3 +....)^(r - 1)然后再变形：X^(K * (r - 1))  * (1/(1 - x))^(r - 1)&#8230;&#8230;然后参照Matrix67大神的日志，展开后面那项：1/(1-x)^n=1+C(n,1)x^1+C(n+1,2)x^2+C(n+2,3)x^3+...+C(n+k-1,k)x^k+...我们知道，要求长度为len的可行数目，也就是要X^Len项前面的系数，然后，由于前面提取出来了一个K * (r - 1)，也就是去后面找len - K * (r - 1) 项的系数&#8230;&#8230;也就是说，令pow = len - K * (r - 1)，答案就是C(r - 1 + pow - 1, pow)&#8230;&#8230;不过这还没完，因为咱们要拼成的长度是len，而总的长度是N，需要乘上这个长度len的开头位置的可能数&#8230;&#8230;另外还需要特殊处理：咱们在处理的时候，是先用r - 1个拼接成长度为Len的一个大段，再堵上最后一个&#8230;&#8230;当r == 1需要特判&#8230;&#8230;代码： 1 #include <cstdio> 2 #include <cstring> 3  4 typedef long long Long; 5 const Long MOD = 1000000007; 6  7 Long F[1010][1010]; 8 Long C[2010][2010]; 9 Long S(int n,int m) {10     if (n == m || m == 1) return 1LL;11     if (F[n][m] > 0) return F[n][m];12     return F[n][m] = (m * S(n - 1, m) % MOD + S(n - 1, m - 1)) % MOD;13 }14 void init() {15     for (int i = 0; i <= 2000; i++) {16         for (int j = 0; j <= i; j++) {17             if (j == 0) C[i][j] = 1;18             else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;19         }20     }21 }22 int n,r,k,m;23 24 int main() {25     memset(F,0xff,sizeof(F));26     init();27     while (scanf("%d%d%d%d",&amp;n,&amp;r,&amp;k,&amp;m) > 0) {28         if (r == 1) {printf("%d\n",n); continue;}29         Long ans = 0;30         for (int i = 1; i <= m &amp;&amp; i <= r; i++) {31             ans = (ans + S(r,i)) % MOD;32         }33         Long tmp = 0;34         for (int len = k * (r - 1); len < n; len++) {35             int left = n - len;36             int pow = len - k * (r - 1);37             // r > 1 !!38             tmp = (tmp + left * C[r - 1 + pow - 1][pow]) % MOD;39         }40         ans = ans * tmp % MOD;41         printf("%lld\n",ans);42     }43     return 0;44 }