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

题目截图

在这里插入图片描述

题目翻译

在这里插入图片描述

题目分析

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

go代码

// LUOGU_RID: 159342370
package main

import (
	. "fmt"
	"io"
	"math/bits"
	"os"
)

// https://space.bilibili.com/206214
func cf451E(in io.Reader, out io.Writer) {
	const mod = 1_000_000_007
	pow := func(x, n int) int {
		res := 1
		for ; 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 %= mod
		p, q := 1, 1
		for i := 1; i <= k; i++ {
			p = p * (n - i + 1) % mod
			q = q * i % mod
		}
		return p * pow(q, mod-2) % mod
	}

	var n, s, tot, ans int
	Fscan(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 := s
		for 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 := 1
	for ; 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 %= mod
	p, q := 1, 1
	for i := 1; i <= k; i++ {
		p = p * (n - i + 1) % mod
		q = q * i % mod
	}
	return p * pow(q, mod-2) % mod
}