容斥原理

用途：难以直接正面解决，却可以围魏救赵解决的问题
核心：设计出快速查询若干集合交集数量的问答系统
1.https://www.luogu.com.cn/problem/P1450
这道题，第一眼是多重背包问题，但是再一眼，在线查询，且数据量大，背包会超时，所以不能是简单的背包问题。
遇到问答题，算出答案的方法肯定要快速，最好是那种预处理过的或者是直接离线解的或者是复用数据
但是这道题钱数都不一样，就钱的面值固定怎么处理？
钱的面值固定，且种类少，可以当做一个切入点。那如何复用数据呢？
思路卡壳，不能每次都打一个dp表直接硬刚，但是可能性就是这么写的，那就打一张表？
一张表怎么打呢？咳咳，正的不行，那就曲线救国！
曲线救国可行度分析：1）不管有没有超过钱数量要求，用完全背包完成任务 可行性up! O(410^5)
2) 求某一或几张超出限制 用dp[s-（n+1）v];就是总钱数-（限制钱数+1）钱的面值 可行性up! O(1)
那现在就是我们的容斥大法上场了,
2.https://leetcode.cn/problems/number-of-music-playlists/description/
这个第一个条件有点难搞，要挑就挑软柿子捏，先完成第二个条件。第二个条件就是排列组合，假设选了第A首歌，那么ABCDEF……（省略k个）A（第k+2个位置可以填（n-k）个）因此就是排列数A（n-k）^(n-k-1).设这个功能的函数为f(n)
好，现在观察第一个条件，既然正的难搞就反着，求如果某m首没有播放的情况，那是什么呢，就是f(n-m)的情况，然后就请出容斥大法即可
综上所述：打表查询or不用查询直接公式简化