#2039. 抽奖机

    ID: 2039 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest762来源:qoj.ac数据:公开样例动态规划

抽奖机

抽奖机

题目描述

标题: 抽奖机 - Problem - QOJ.ac

#4916. 抽奖机

Statistics

时间&空间限制

Time Limit: 1.5s 2.5s

Memory Limit: 256MB

题目描述

奆L 有一个神秘的抽奖机,它由 n 个转轮组成。

每个转轮有三个档位,记作0,1,2,转轮的转动与档位关系如下:

  1. 当一个0档位转轮被转过一次,会变成1档位
  2. 当一个1档位转轮被转过一次,会变成2档位
  3. 当一个2档位转轮被转过一次,会变成0档位

一开始所有 n 个转轮都在0档,将所有转轮的集合记作 S。

抽奖机的抽奖器有 m 个模式,每个模式可以用两个数字 ai,bi 描述,表示:

  1. 将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)!种分配集合的方法

  2. 然后将集合A中的转轮转动一次,所有集合B中的转轮转过两次

每次拉下摇杆,抽奖机都会进行转动,一次转动如下:

  1. 从所有模式里选取一个进行;
  2. 从所有可能的转动情况中选择一个进行。

最终,应该有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