RainAir
My OI Blog
RainAir
「Gym100548F」Color

题目大意

题意:现在有 $n$ 个格子和 $m$ 种颜色,问你恰好将这些花盆染成 $k$ 种颜色,且同种颜色不相邻的方案数。答案对 $10^9+7$ 取模, $n,m, \leq 10^9,k \leq 10^6$

心路历程

首先比较 sb 的交了个 $\binom m k k(k-1)^{n-1}$,WA on 2(其实就 $2$ 组数据)…
然后仔细思考一下,发现 $k(k-1)^{n-1}$ 貌似是 $\leq k$ 的??然后我就叫了个 $\binom m k (k(k-1)^{n-1}-(k-1)(k-2)^{n-1})$,WA on 2
稍微理性分析了一下发现这样算太 naive 了,然后改了一下 就 A 了。(今天真是意识模糊的一天)

题解

首先我们来分析一下第二种方法为什么不对:考虑在 $k(k-1)^{n-1}$ 中使用了 $x$ 种颜色的某一种确定的方案被计算的次数:$\binom k x$。显然 $\binom k x – \binom {k-1} x \neq 1$,所以做法萎了。
于是我重新推了一下式子。。发现设 $f_i$ 表示恰好染 $i$ 种颜色的方案,$g_i$ 表示染了 $\leq i$ 中颜色的方案的话,首先 $g_i = i(i-1)^{n-1}$,然后发现它们之间有关系
$$g_n = \sum_{k = 1}^n \binom n i f_i$$
于是立刻有
$$f_n = \sum_{k=i}^n (-1)^{n-i} \binom n i g_i$$
我们要求的答案就是 $\binom m k f_k$
科普小学知识1:暴力算组合数的复杂度是 $O(m)$ 的,可以使用广义定义 $\binom n m = \frac{n^{\underline m}}{m!}$
科普小学知识2:组合数可以快速算一行。(这个算幼儿园知识了吧我就不说了)
所以这题就是个很 ez 的题了。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/802
如文中无特殊声明,本文采用 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

「Gym100548F」Color
题目大意 题意:现在有 $n$ 个格子和 $m$ 种颜色,问你恰好将这些花盆染成 $k$ 种颜色,且同种颜色不相邻的方案数。答案对 $10^9+7$ 取模, $n,m, \leq 10^9,k \leq 10^6$ 心路历程 首…
扫描二维码继续阅读
2019-08-27
标签
近期评论