一个的网格,每步只能向下或者向右走.有 k 个被 ban 掉的点,不能经过.问左上走到右下的方案数.
考虑容斥.设表示经过第个 banned 点,在这之前不走 banned 点,之后随便走的方案数.
求也可以对前半部分使用容斥,即第一次走到第个 banned 点,在这之前不走 banned 点,然后随便走,走到第个 banned 点,然后随便走的方案数.这样用经过的总方案数减就能求.
有个体积为的物品,对于每一个,求出没有第个物品的情况下剩下个物品填满容积为的背包的方案数.
可以直接大除法,从低位往高位除.
从它的组合意义去理解的话,设表示所有物品的方案数背包,而表示缺失第个物品的方案数背包.则显然有.现在我们知道,要求,于是直接即可.
大除法也可以看成是从小到大的 DP 转移.
一个长度为 n 的序列,满足每个元素都是 [1k] 内的整数 且对于相邻的两个元素 有或.求这样的序列的个数模.
考虑容斥,转化为无限制减去.这可以 DP,表示长度为的序列的方案数,则转移的时候枚举这一段是整除序列,然后是无限制关系.由于的长度是的,因此预处理一下,直接转移就行了.
给一棵有根树,求拓扑序方案数.
算概率去理解.
注:相当于 u 的儿子子树大小之和.
带标号无向连通图计数.
设带标号的无向图个数为,无向不连通图个数为,无向连通图个数为.
并联时不考虑并联线路之间的顺序(即他们都是相同的)
现在给定边的数量,问串并联网络的个数.
这是一道小清新的题.事实上你发现,一个串并联网络具有树形结构.一个串联的整体下有若干个并联的线路,一个并联的整体下有若干个串联的线路.因此这就是一个树的结构,且奇偶层分别为串联和并联的结点.于是你根本不用管串联并联的问题,直接对树计数然后答案乘 2 即可.
一个串联或者并联结构至少有两条线路.因此我们要求的是每个内部结点的儿子数大于 1的树的个数.设表示叶子结点总数为 n 的树的个数.
由于你不考虑兄弟结点间的顺序,因此就要有一个单调性的限制.于是再定义表示叶结点数为 i,根结点的每颗子树最多包含 j 个叶子的树的方案数.显然,可以枚举包含 j 个叶子的子树数量求 g.假设有 k 个子树包含 j 个叶子,于是就相当于在个方案中选 k 个,可重复.这就是一个不定方程非负整数解的问题,答案为: