题目背景

HAOI2018 Round2 第二题

题目描述

为了报答小 C 的苹果, 小 G 打算送给热爱美术的小 C 一块画布, 这块画布可 以抽象为一个长度为 

N

 的序列, 每个位置都可以被染成 

M

 种颜色中的某一种.

然而小 C 只关心序列的 

N

 个位置中出现次数恰好为 

S

 的颜色种数, 如果恰 好出现了 

S

 次的颜色有 

K

 种, 则小 C 会产生 

W_k

 的愉悦度.

小 C 希望知道对于所有可能的染色方案, 他能获得的愉悦度的和对 

1004535809

 取模的结果是多少.

输入输出格式

输入格式:

从标准输入读入数据. 第一行三个整数 

N, M, S

 .

接下来一行 

M + 1

 个整数, 第 

i

 个数表示 

W_{i-1}

 .

输出格式:

输出到标准输出中. 输出一个整数表示答案.

输入输出样例

输入样例#1: 复制

输出样例#1: 复制

输入样例#2: 复制

输出样例#2: 复制

说明

特殊性质: 

\forall 1 \le i \le m, W_i = 0

对于 

100\%

 的数据, 满足 

0 \le W_i < 1004535809

 

设lim=min(m,n/s)即 最多放多少个S长度的颜色 假设现在有k个s长度的颜色尝试求方案数 $C_{m}^{k}\times (C_{m}^{s}\times C_{m-s}^{s})\times (m-k)^{n-ks}$ 可以发现这样会有重复的计算 那么不妨分成两段来计算 设g[m][n]表示不包含k种颜色中的颜色的随意组合且不会再出现s长度这种情况的方案数 那么我们可以把后面这段来容斥计算 带入 $\sum\limits_{i=0}^{lim}\frac{m!}{(m-i)!\times i!} \frac{n!}{(s!)^i(n-s)!}\sum\limits_{j=0}^{m-i}(-1)^{j}\frac{(m-i)!}{(m-i-j)!j!}\times \frac{(n-is)!}{(s!)^j(n-js-is)!}\times (m-i-j)^{n-js-is}$ 考虑i和lim互换是并不影响什么的所以我们将i看成lim-i此外 将j替换为j-i $\sum\limits_{i=0}^{lim}\frac{m!}{(m-i)!i!}\frac{n!}{(s!)^i(n-s)!}\sum\limits_{j=i}^{lim}(-1)^{j-i}\frac{(m-i)!}{(m-j)!(j-i)!}\times\frac{(n-is)!}{(s!)^{j-i}(n-js-is)!}(m-j)^{n-is}$ 考虑构造卷积形式 $m!n!\sum\limits_{j=1}^{lim}\frac{(m-j)^{n-js}}{(m-j)!(s!)^j(n-js)!}\sum\limits_{i=0}^{j}\frac{w_i}{i!}\frac{(-1)^{j-i}}{(j-i)!}$

 

分类: ntt容斥

elijahqi

退役了 现在在商院 偶尔打CF,有时有ACM regional也去玩一下

发表评论