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

2024-05-23 23:52

本文主要是介绍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
}

总结

容斥原理的应用(根据个数,符号交替)

这篇关于CF451E: Devu and Flowers(容斥原理 + 考虑反面 + golang组合模版)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/996779

相关文章

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

Java的IO模型、Netty原理解析

《Java的IO模型、Netty原理解析》Java的I/O是以流的方式进行数据输入输出的,Java的类库涉及很多领域的IO内容:标准的输入输出,文件的操作、网络上的数据传输流、字符串流、对象流等,这篇... 目录1.什么是IO2.同步与异步、阻塞与非阻塞3.三种IO模型BIO(blocking I/O)NI

golang 日志log与logrus示例详解

《golang日志log与logrus示例详解》log是Go语言标准库中一个简单的日志库,本文给大家介绍golang日志log与logrus示例详解,感兴趣的朋友一起看看吧... 目录一、Go 标准库 log 详解1. 功能特点2. 常用函数3. 示例代码4. 优势和局限二、第三方库 logrus 详解1.

JAVA封装多线程实现的方式及原理

《JAVA封装多线程实现的方式及原理》:本文主要介绍Java中封装多线程的原理和常见方式,通过封装可以简化多线程的使用,提高安全性,并增强代码的可维护性和可扩展性,需要的朋友可以参考下... 目录前言一、封装的目标二、常见的封装方式及原理总结前言在 Java 中,封装多线程的原理主要围绕着将多线程相关的操

kotlin中的模块化结构组件及工作原理

《kotlin中的模块化结构组件及工作原理》本文介绍了Kotlin中模块化结构组件,包括ViewModel、LiveData、Room和Navigation的工作原理和基础使用,本文通过实例代码给大家... 目录ViewModel 工作原理LiveData 工作原理Room 工作原理Navigation 工

Java的volatile和sychronized底层实现原理解析

《Java的volatile和sychronized底层实现原理解析》文章详细介绍了Java中的synchronized和volatile关键字的底层实现原理,包括字节码层面、JVM层面的实现细节,以... 目录1. 概览2. Synchronized2.1 字节码层面2.2 JVM层面2.2.1 ente

Golang中拼接字符串的6种方式性能对比

《Golang中拼接字符串的6种方式性能对比》golang的string类型是不可修改的,对于拼接字符串来说,本质上还是创建一个新的对象将数据放进去,主要有6种拼接方式,下面小编就来为大家详细讲讲吧... 目录拼接方式介绍性能对比测试代码测试结果源码分析golang的string类型是不可修改的,对于拼接字

MySQL的隐式锁(Implicit Lock)原理实现

《MySQL的隐式锁(ImplicitLock)原理实现》MySQL的InnoDB存储引擎中隐式锁是一种自动管理的锁,用于保证事务在行级别操作时的数据一致性和安全性,本文主要介绍了MySQL的隐式锁... 目录1. 背景:什么是隐式锁?2. 隐式锁的工作原理3. 隐式锁的类型4. 隐式锁的实现与源代码分析4

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

MySQL中Next-Key Lock底层原理实现

《MySQL中Next-KeyLock底层原理实现》Next-KeyLock是MySQLInnoDB存储引擎中的一种锁机制,结合记录锁和间隙锁,用于高效并发控制并避免幻读,本文主要介绍了MySQL中... 目录一、Next-Key Lock 的定义与作用二、底层原理三、源代码解析四、总结Next-Key L