BZOJ 3294: [Cqoi2011]放棋子

正文索引 [隐藏]

Description

Input

输入第一行为两个整数n, m, c,即行数、列数和棋子的颜色数。第二行包含c个正整数,即每个颜色的棋子数。所有颜色的棋子总数保证不超过nm

Output

输出仅一行,即方案总数除以 1,000,000,009的余数。

Sample Input

4 2 2
3 1

Sample Output

8

HINT

N,M<=30 C<=10 总棋子数<=250

题解

F[i][x][y]表示计算到第i种颜色,已经占了x行y列的方案数!
G[i][x][y]表示第i种颜色刚好占据x行y列方案数!
F[i][x+ux][y+uy]=simga{F[i-1][ux][uy]C(x,n-ux)C(y,m-uy)*G[i][x][y]}
Orz一开始似乎计算G的方法错了?但是似乎仔细想想没有错了OwQ!求神犇指出错误!