QOJ.ac

QOJ

Time Limit: 2.5 s Memory Limit: 256 MB Total points: 100
Statistics

时间&空间限制

Time Limit: 1.5s 2.5s

Memory Limit: 256MB

题目描述

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

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

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

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

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

  1. 将$S$分为三个集合$A,B,C$,即满足:

    • $A\cap B,A\cap B,B\cap C=\emptyset,A\cup B\cup C=S,|A|=a_i,|B|=b_i$

      其中$|A|$表示集合$A$的大小,容易发现一共有$\cfrac{n!}{a_i!b_i!(n-a_i-b_i)!}$种分配集合的方法

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

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

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

最终,应该有$\displaystyle \sum_{i=1}^m \cfrac{n!}{a_i!b_i!(n-a_i-b_i)!}$种方案,在这样的所有方案中选择一个。

现在奆$\mathscr{L}$通过py手段得知了所有的模式,但是ta依然无法控制抽奖机的结果。

自暴自弃的ta决定连续乱拉$k$次拉杆,而并且在此之前,ta暴怒地逼问你:

最终抽奖机恰好有 $i$ 个转轮在 $1$ 档,$j$ 个转轮在 $2$ 档的方案数。

由于答案可能非常大,请输出其 $\mod 10^9+9$ 的结果。

输入格式

第一行三个正整数 $n,m,k$,表示转轮个数,模式个数,奆$\mathscr{L}$ 拉拉杆的次数。

然后 $m$ 行,每行两个整数 $a_i,b_i$,描述 奆$\mathscr{L}$ 通过py得知的一个模式。

输出格式

输出 $n+1$ 行,第 $i$ 行输出 $n+2-i$ 个数。

第 $i$ 行第 $j$ 个数表示:最终抽奖机恰好有 $i$ 个转轮在 $1$ 档,$j$ 个转轮在 $2$ 档的方案数,$\mod 10^9+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 $\rightarrow$ 02,11,00,21

10 $\rightarrow$ 11,20,21,00

02 $\rightarrow$ 00,12,01,22

20 $\rightarrow$ 21,00,22,10

数据规模与约定

本题不采用子任务评测。

对于所有数据,满足 $n\leq 120,m\leq 10^5,k\leq 10^{18},\forall 0\leq a_i,b_i\leq n,\forall a_i+b_i\leq 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$ $10^9$
6 $20$ $10^{18}$
7 $40$ $10^5$ $20$ $b_i=0$
8 $10^9$
9 $50$ $50$
10 $40$ $10^5$
11 $50$ $10^{18}$
12 $10$ $b_i=0$
13 $80$ $100$
14 $100$
15 $100$ $10^{9}$
16 $10^5$
17 $10^{18}$
18 $110$
19
20 $120$