CF451E: Devu and Flowers（容斥原理 + 考虑反面 + golang组合模版）

题目截图

题目翻译

题目分析

正难则反，考虑所有不符合的例子
由于n很小，所以可以状态压缩二进制遍历完全部不符合例子的组合
对于不符合的例子，假设其中第i个不符合，那么就消耗掉fi + 1个球
以此类推，减剩下s2个球
这时候使用隔板法分给n个箱子，加上n - 1个挡板，就是comb(s2 + n - 1, n - 1)
对于容斥原理，奇偶个数要对应不同的符号，这里需要注意

go代码

// LUOGU_RID: 159342370
package mainimport (. "fmt""io""math/bits""os"
)// https://space.bilibili.com/206214
func cf451E(in io.Reader, out io.Writer) {const mod = 1_000_000_007pow := func(x, n int) int {res := 1for ; n > 0; n /= 2 {if n%2 > 0 {res = res * x % mod}x = x * x % mod}return res}comb := func(n, k int) int {if n < k {return 0}n %= modp, q := 1, 1for i := 1; i <= k; i++ {p = p * (n - i + 1) % modq = q * i % mod}return p * pow(q, mod-2) % mod}var n, s, tot, ans intFscan(in, &n, &s)a := make([]int, n)for i := range a {Fscan(in, &a[i])tot += a[i]}if tot < s {Fprint(out, 0)return}for i := uint(0); i < 1<<n; i++ { // 表示这个组合中为1的盒子是超过ai个的（违法）s2 := sfor j, v := range a {if i>>j&1 > 0 {s2 -= v + 1 // 现分配ai+1个}}res := comb(s2+n-1, n-1)     // n-1个挡板表示分成n组，剩下s2个球if bits.OnesCount(i)%2 > 0 { // 根据个数确定正负号, 容斥原理res = -res}ans += res}Fprint(out, (ans%mod+mod)%mod)
}func main() { cf451E(os.Stdin, os.Stdout) }

快速幂以及组合数的go模版

const mod = 1_000_000_007
pow := func(x, n int) int {res := 1for ; n > 0; n /= 2 {if n%2 > 0 {res = res * x % mod}x = x * x % mod}return res
}
comb := func(n, k int) int {if n < k {return 0}n %= modp, q := 1, 1for i := 1; i <= k; i++ {p = p * (n - i + 1) % modq = q * i % mod}return p * pow(q, mod-2) % mod
}

总结

容斥原理的应用（根据个数，符号交替）