RainAir
My OI Blog
RainAir
「ARC102E」Stop. Otherwise...

题目大意

有 $N$ 个 不可区分的 $K$ 面骰子。
对于每个 $i = 2, 3, \cdots , 2K$,求有多少种方案使得:任意两个点数不同 的骰子朝上的面之和不为 $i$。
答案对 $998244353$ 取模。
$2 \leq N \leq 2000,1 \leq K \leq 2000$。

题解

我们考虑对于 $i=x$ 怎么去计算答案 $ans$,考虑容斥,设 $cnt$ 表示$i+j=x$ 的无序对个数,那么答案就是
$ans = \sum_{i=0}^{cnt} (-1)^i \binom {cnt} {i} \binom {n-2i+k-1}{k-1}$
后面那个组合数是因为骰子是无序的,我们可以转化为求每种点数出现了多少次,插板一下得到的这个式子。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/888
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「ARC102E」Stop. Otherwise...
题目大意 有 $N$ 个 不可区分的 $K$ 面骰子。 对于每个 $i = 2, 3, \cdots , 2K$,求有多少种方案使得:任意两个点数不同 的骰子朝上的面之和不为 $i$。 答案对 $998244353$ 取模。 $2 \l…
扫描二维码继续阅读
2019-10-17
标签
近期评论