[NKU]sweet @ Google && TopCoder && CodeForces

  BlogJava :: 首页 :: 联系 :: 聚合  :: 管理
  33 Posts :: 1 Stories :: 15 Comments :: 0 Trackbacks
这题比赛时候过得很纠结……最后还是学长过的……比赛时候脑子可能不够清楚,一直WA……
首先,这个题要分成两个部分解决:
第一部分:从n个东西里面取出r个,每个间距至少为 k (1~K不行,1~K + 1行)
第二部分:将这r个东西分成至多m组,可以有空组
第二部分貌似好久之前搞OI的时候干过……贴过来:
N球放在M个盒子里,求共有多少种放法

但是有3个不同的条件 :N个球是否相同,M个盒子是否相同,是否允许有盒子空着

球和球

盒和盒

空盒

情况数

有区别

有区别

有空盒

mn

有区别

有区别

无空盒

Msn,m

有区别

无区别

有空盒

S(n,1)+s(n,2)+…+s(n,m),n>=m

S(n,1)+s(n,2)+…+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数……
递推公式:
1 int S(int n,int m) {
2     if (n == m || m == 1return 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 +1的可行解……
而r - 1根棍子,拼成长度为Len 的可行解数目,就是(X^K + X^(K + 1) + X^(K + 2) + .....) ^ (r - 1),这个多项式,展开之后,X^Len项前面的系数……
不过……由于数据范围,直接搞是不成的……
于是提取,变形:X^(K * (r - 1))  * (1 + X + X^2 + X ^3 +....)^(r - 1)
然后再变形:X^(K * (r - 1))  * (1/(1 - x))^(r - 1)……
然后参照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) 项的系数……
也就是说,令pow = len - K * (r - 1),答案就是C(r - 1 + pow - 1, pow)……
不过这还没完,因为咱们要拼成的长度是len,而总的长度是N,需要乘上这个长度len的开头位置的可能数……
另外还需要特殊处理:咱们在处理的时候,是先用r - 1个拼接成长度为Len的一个大段,再堵上最后一个……当r == 1需要特判……
代码:
 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 == 1return 1LL;
11     if (F[n][m] > 0return 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",&n,&r,&k,&m) > 0) {
28         if (r == 1) {printf("%d\n",n); continue;}
29         Long ans = 0;
30         for (int i = 1; i <= m && 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 }
posted on 2011-09-18 22:56 sweetsc 阅读(1919) 评论(3)  编辑  收藏 所属分类: ACM/ICPC学习心得

Feedback

# re: 2011ACM北京网络预选赛 F Machine scheduling (BUPT 216) 2011-09-19 08:53 tb
恩 不错啊   回复  更多评论
  

# re: 2011ACM北京网络预选赛 F Machine scheduling (BUPT 216) 2011-09-19 08:58 sxj_program
Oops, What a pity!
So tired yesterday that do not read this problem, We could have solved it much earlier ==!  回复  更多评论
  

# re: 2011ACM北京网络预选赛 F Machine scheduling (BUPT 216) 2011-09-19 09:58 [NKU]sweet
@sxj_program
难道司君是无名英雄?……  回复  更多评论
  


只有注册用户登录后才能发表评论。


网站导航: