计数问题首推容斥,然后再解决一些棘手的组合问题? 题目描述 大中锋的学院要组织学生参观博物馆,要求学生们在博物馆中排成一队进行参观。 他的同学可以分为四类:一部分最喜欢唱、一部分最喜欢跳...
容斥原理
洛谷 P4336 [SHOI2016]黑暗前的幻想乡 题解【矩阵树定理】【容斥】
矩阵树定理明明只是个记结论的东西对吧..(大雾 题目描述 四年一度的幻想乡大选开始了,最近幻想乡最大的问题是很多来历不明的妖怪涌入了幻想乡,扰乱了幻想乡昔日的秩序。但是幻想乡的建制派妖怪(人类...
数学小知识点【学习笔记】 upd on 2019.7.10
一、线性求逆元 1. $1\sim n$ 的逆元 单独一个数 $\bmod p$ 的逆元是可以用费马小定理($p$ 为质数)或 exgcd 在 $O(\log p)$ 的复杂度内求的。但是如果要求 $1\sim n$ 的逆元,其实用不到 $O(n\log n)$。正如 $O...
洛谷 P2184 贪婪大陆 题解【线段树】【容斥原理】
大家写的题解跟我都不一样啊hhh 题目背景 面对蚂蚁们的疯狂进攻,小FF的Tower defence宣告失败……人类被蚂蚁们逼到了Greed Island上的一个海湾。现在,小FF的后方是一望无际的大海, ...
NOIp模拟赛 数字【DP】【背包】【递推】【容斥原理】
DP思路有点难想的一个DP套递推题。为啥还要容斥原理 题目描述 一个数字被称为好数字当他满足下列条件: 1. 它有2*n个数位,n是正整数(允许有前导0)。 2. 构成它的每个数字都在给定的数字集合...