#2039. 抽奖机
抽奖机
抽奖机
题目描述
标题: 抽奖机 - Problem - QOJ.ac
#4916. 抽奖机
时间&空间限制
Time Limit: 1.5s 2.5s
Memory Limit: 256MB
题目描述
奆L 有一个神秘的抽奖机,它由 n 个转轮组成。
每个转轮有三个档位,记作0,1,2,转轮的转动与档位关系如下:
- 当一个0档位转轮被转过一次,会变成1档位
- 当一个1档位转轮被转过一次,会变成2档位
- 当一个2档位转轮被转过一次,会变成0档位
一开始所有 n 个转轮都在0档,将所有转轮的集合记作 S。
抽奖机的抽奖器有 m 个模式,每个模式可以用两个数字 ai,bi 描述,表示:
-
将S分为三个集合A,B,C,即满足:
-
A∩B,A∩B,B∩C=∅,A∪B∪C=S,|A|=ai,|B|=bi
其中|A|表示集合A的大小,容易发现一共有n!ai!bi!(n−ai−bi)!种分配集合的方法
-
-
然后将集合A中的转轮转动一次,所有集合B中的转轮转过两次
每次拉下摇杆,抽奖机都会进行转动,一次转动如下:
- 从所有模式里选取一个进行;
- 从所有可能的转动情况中选择一个进行。
最终,应该有m∑i=1n!ai!bi!(n−ai−bi)!种方案,在这样的所有方案中选择一个。
现在奆L通过py手段得知了所有的模式,但是ta依然无法控制抽奖机的结果。
自暴自弃的ta决定连续乱拉k次拉杆,而并且在此之前,ta暴怒地逼问你:
最终抽奖机恰好有 i 个转轮在 1 档,j 个转轮在 2 档的方案数。
由于答案可能非常大,请输出其 mod109+9 的结果。
输入格式
第一行三个正整数 n,m,k,表示转轮个数,模式个数,奆L 拉拉杆的次数。
然后 m 行,每行两个整数 ai,bi,描述 奆L 通过py得知的一个模式。
输出格式
输出 n+1 行,第 i 行输出 n+2−i 个数。
第 i 行第 j 个数表示:最终抽奖机恰好有 i 个转轮在 1 档,j 个转轮在 2 档的方案数,mod109+9。
输入输出样例
machine1.in
2 2 2
0 1
1 0
machine1.out
4 2 2
2 4
2
machine2.in
2 2 2
0 1
2 0
machine2.out
0 0 3
6 0
0
machine3.in
3 6 4
1 2
2 0
1 1
0 1
1 0
0 3
machine3.out
4884 14295 14508 4873
14529 29202 14331
14313 14526
4860
样例解释
对于样例1,容易发现一次有4种可能 01,10,02,20
两次一共有16种可能
01 → 02,11,00,21
10 → 11,20,21,00
02 → 00,12,01,22
20 → 21,00,22,10
数据规模与约定
本题不采用子任务评测。
对于所有数据,满足 n≤120,m≤105,k≤1018,∀0≤ai,bi≤n,∀ai+bi≤n 。
给定的m个模式之间可能有重复 。
下表列出了所有20个测试点n,m,k的上限以及数据的特殊性质:
n m k 特殊性质 1 3 6 4 无 2 5 10 10 3 8 3 5 4 20 20 20 5 17 500 109 6 20 1018 7 40 105 20 bi=0 8 109 9 50 50 无 10 40 105 11 50 1018 12 10 bi=0 13 80 100 14 100 15 100 109 无 16 105 17 1018 18 110 19 20 120
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
2 2 2
0 1
1 0
4 2 2
2 4
2