snday2 组合数与容斥

a*b，以ab形式记录

组合数

选择模拟/非空标记/一维定点

CNM 

        从n个数中选取m个无排列数，组成A列

        针对任一单调递增的A串，记为A1，

        第一个有n种可能，第二个有n-1种……第m个有n-m+1种

        则A1共有n*(n-1)*(n-2)*…*(n-m+1)种可能，即为n!/(n-m)!

        与A1元素相同的串中，

        第一个有m种可能，第二个有m-1种……第m个有1种，

        则有m!种可能，而在计数时，归为一类

        综上，A列可能数为n!/((n-m)!*m!)

递推 C(n,m)=C(n-1,m-1)+C(n-1,m)

边界 C(n,0)=1

特性 C(n,m)=C(n,n-m)

        m*C(n,m)=n*C(n-1,m-1)

        ∑i=0-->n C(n,i)=2^n

        C(n,m)=∑i=0-->n−1 C(i,m−1)

证明

        F.借由CNM模拟得

        S.通过原始公式推得

代码实现

inline int C(int n,int m) {
	if(n==m||m==0) return 1;
	return C(n-1,m-1)+C(n-1,m); }//递归

inline int C_(int n,int m) {
	if(n==m||m==0) return 0;
	return C1(n,m-1)*(n-m+1)/m; }//递归优化

inline int C_second(int n,int m) {
	if(n==m||m==0) return 1;
	for(ri i=0; i<=n; ++i)
		for(ri j=min(i,m); j>=0; --j)
			if(i==j||j==0)
				dp[j]=1;
			else
				dp[j]=dp[j]+dp[j-1]; }//动态规划

应用

        卡特兰(进出栈问题) 

                存在一坐标图，将x轴定义为输入轴，即进栈，将y轴定义为输出轴，即出栈

                则每一次进栈为在x正半轴方向移动一单位，出栈为相似的y轴操作

                得满足进出操作且出栈序列不同的数字，

                即为(0,0)到(n,n)的直线中不越过y=x的部分

                由于对称性，易得结果C(2n,n+1)

容斥

正难则反/加减效果/网状模拟

概述

        计算包含于某内容中的所有对象的数目

        后把重复计算的数目排斥出去，使计算的结果无漏无重

本土化

        具有同一功能的个体组成集合，共同行使功能

        由于个体功能的可叠加性，在计数时去除叠加过的功能

钦定

        定位功能主体，进而反射行使功能的个体

标记

        动态规划打表反推，参考杨辉三角

——————————