@组合数学-计数问题二-个人总结
i207M
·
·
个人记录
常用技巧
当我们需要计算满足多个限制条件的方案数时，设两个数组f（满足较弱的限制）和g（答案）互推是一个好方法。
小Trick
对于求恰好 k 个的方案数，并且贡献为 x^k 的形式
可以利用二项式定理展开
x^k=\sum_{i=0}^{k}\binom{k}{i}(x-1)^i
含义就是，我们枚举所有的子集E，然后贡献加上(x-1)^{|E|}即可，这样可以省去容斥
完全二分图的生成树个数
n^{m-1}m^{n-1}
有限制的计数-立马想到容斥原理！
k{n\choose k}=n{n-1\choose k-1}
高维容斥原理
CF997C
有一个 n \times n ( n \leq 10^6 )的正方形网格，用红色，绿色，蓝色三种颜色染色，求有多少种染色方案使得至少一行或一列是同一种颜色。
我们可以枚举有多少行相同，有多少列相同，但是二维的容斥系数如何配呢？事实上，就是直观的方式：
ans = \sum_{i=0 \ldots n, j=0 \ldots n, i + j > 0} C_n^i C_n^j (-1)^{i + j + 1} f(i, j)
## 好题-【牛客挑战赛30D】小A的昆特牌
从纯组合数，转化为平面上的移动，然后改变视角，枚举它经过横坐标l时的纵坐标y，$y\in[0,n-1]$，这样就能满足要求。
组合数求和，一维比较小 -> 转化为平面上的点。
# 求本质不同的方案数
Polya 原理。
容斥让每种方案贡献为 1。
设计DP方法让每种方案在字典序最小的地方被算。
# 发现式子推不动了——从组合意义的角度去考虑！！！
### 遇到卡特兰数+限制——括号序、出栈序，尝试建出来一棵树，对区间进行“树形DP”
## 逆序对排列计数
统计长为n，有k个逆序对的排列数（$n,k\le 10^5$）
观察暴力的DP式子，可以把模型转化为有n个变量，范围$[0,i-1]$，求它们和为k的方案数
也就是求$\prod (1-x^i)$，取Ln后$O(n\log n)$算即可。
还有一种更加优美的方法：
观察到多项式的乘积就是01背包，第i个物品的体积为i，选了j个物品的贡献是$(-1)^j
可以得到DP方程：
dp[i][j]=dp[i-1][j-i]-dp[i-1][j-i-1]+dp[i-1][j-(n+1)]
第一项是集体+1，第二项是集体+1后加入一个1，第三项是减去超过n的贡献。注意+-号。
注意是循环到\sqrt{2k}，不是\sqrt{2n}。。。
g[0]=f[0][0]=1;
for(ri i=1; i<=blo; ++i)
for(ri j=i; j<=K; ++j)
{
dec(f[i][j],f[i-1][j-i]);
inc(f[i][j],f[i][j-i]);
if(j>=n+1) inc(f[i][j],f[i-1][j-n-1]);
inc(g[j],f[i][j]);
}
int ans=0;
for(ri i=0; i<=K; ++i)
inc(ans,mul(C(i+n-1,n-1),g[K-i]));
out(ans);
配系数求和
如果你可以方便的求S(n)=\sum^n_i f[i]，如何求\sum_i^ni\times f[i]甚至\sum_i^ni^2\times f[i]？
累加法！
\sum_i^n(n-i+1)\times f[i]=\sum_i^n S(i)
Every Day is a Holiday（PE 645）
Byteland中，一年有恰好d天。一年中的有些日子是假日，定义如下：
- 皇帝出生的日子是假日
- 如果一天的前一天和后一天都是假日，那么它也是假日
开始没有假日，接下来会上任若干皇帝。假设每个皇帝的生日在一年中均匀随机，期望要多少任皇帝才能让一年中的每一天都是假日呢？
输出答案mod 998244353，1≤d≤10^5。
每天都是假日等价于排序后相邻两个皇帝的生日的间隔\le 2，这可以用组合数算出概率。通过累加，把贡献凑出来。
生成函数互不相同的卷积
比方说我现在有一个生成函数A（可以视作有大小的物品的集合），现在我要从中选3个互不相同的物品，求方案数。
如果直接A^3的话，我们会选择重复的，于是自然的我们需要容斥，事实上，这就是斯特林反演的过程！式子具体是A(x)^3-3A(x^2)A(x)+2A(x^3)
长为n的排列，LIS=n-1有(n-1)^2种情况。