组合数学-计数问题-个人总结

· · 个人记录

在模运算时，指数取模时一定要对\phi取

别忘了容斥！！！

盒子与球

洛谷日报

网格放石子

在 N 条水平线与 M 条竖直线构成的网格中，放 K 枚石子，每个石子都只能放在网格的交叉点上。问在最优的摆放方式下，最多能找到多少四边平行于坐标轴的长方形，它的四个角上都恰好放着一枚石子。 0 < N, M ≤ 30000

很显然我们要把石子放在一起，摆成一个尽量大的矩形，然而我们无法确定矩形的边长，所以，我们需要枚举边长；对于剩下的点，就依次放在下一行；规律还是比较简单的；

注意：要枚举边长，边长不是越长越好；

int sol(int n, int m) {
    int x, y, ans = 0;
    for (ri i = 2, mi = min(n, k); i <= mi; ++i) {
        x = k / i - 1;
        y = k % i - 1;
        if (x + 1 >= m) x = m - 1, y = 0;
        ans = max(x * (x + 1) / 2 * i * (i - 1) / 2 + y * (y + 1) / 2 * (x + 1), ans);
    }
    return ans;
}

连边计数

黑点和白点各有i个，每个黑点可以向一个白点连一条边或不连，方案数为i!，原因是每个连边方式都对应一个1-N的排列；

染色计数

给定N个点，M种颜料，每个点染色，要求每连续M个点不能颜色都不相同，求方案数；

m<=n<=10^16

设f[i][j]表示到i位置，i及之前连续颜色不同的最长长度为j的方案数；

转移：再放置一个不同颜色，有m-j种选择，f[i+1][j+1]+=f[i][j]×(m-j),j+1!=m

放置一个相同颜色，枚举是[i-j+1,i]中的哪一种颜色，长度会减小，f[i+1][k]+=f[i][j],k=[1,j]

转移与i无关，矩阵乘法优化；

CF294C Shaass and Lights

有n盏灯，(0<=n<=1000),有m盏已经点亮，每次只能点亮与已经点亮的灯相邻的灯，求总方案数，答案对1e9+7取模

我们可以借助已经被点亮的灯作为分界点，找到若干个长度不为0的开区间。

对于两边都有开着的灯的区间，我们点亮它每次可以点亮最左边一盏或者最右边一盏，而最后一盏灯只有一种方法，所以点亮长度为len的区间的方案数为：2^(len-1)

特别地，对于两端的区间（一边有灯开着，一边是边界（1或者n）），只有一种方案数（顺着一路点下去）

根据乘法原理，可以先计算出ans*=2^(len2-1)2^(len-2-1)...2^(len(cnt-1)-1)注意开始的时候是i=2，最后一段是i=cnt-1；（最初最末两端算上是没有意义的）

但是由于点灯的时候可以交叉在每个区间内点灯，所以这样的ans还是少了很多。

所以我们重新这样考虑： 考虑将每个区间内考虑成颜色相同的len个球，不同区间球的颜色不同。每一个排列可以当做是一个指令，不同的合法的指令是不同的方案数。

容易知道最初的方案数为：（n-m）！我们将它处理成多重集合的排列，(n-m)!/len1!len2!...lencnt!。这样保证了每个区间内的同一种颜色的球的“单纯相对顺序”（只是这些球之间交换顺序）变化都算作是一种方案。

但是一个区间内，并不是一种方案，对于len的球数，可以有2^(len-1)种合法排列，利用乘法原理再将它们相乘，就可以得出正确的答案。

[POI2018]Powódź

在地面上有一个水箱，它的俯视图被划分成了n行m列个方格，相邻两个方格之间有一堵厚度可以忽略不计的墙，水箱与外界之间有一堵高度无穷大的墙，因此水不可能漏到外面。已知水箱内每个格子的高度都是[0,H]之间的整数，请统计有多少可能的水位情况。因为答案可能很大，请对10^9+7取模输出。两个情况不同当且仅当存在至少一个方格的水位在两个情况中不同。

神仙般的并查集

先将所有边按高度排序，然后从小到大枚举所有边，用并查集维护格子的连通性。在并查集合并的时候统计一下方案数就好。

具体地，我们用g表示当前连通块的方案数，h表示这个连通块当前的水位高度，设当前水位为now，于是一次合并的贡献就是(g+now-h)*(g'+now-h')。

        if((x = find(x)) != (y = find(y)))
        {
            g[x] = (g[x] + p[i].h - h[x]) * (g[y] + p[i].h - h[y]) % md;
            h[x] = p[i].h;
            f[y] = x;
        }

着色方案

有n个木块排成一行，从左到右依次编号为1~n。你有k种颜色的油漆，其中第i 种颜色的油漆足够涂ci 个木块。所有油漆刚好足够涂满所有木块，即c1+c2+...+ck=n。相邻两个木块涂相同色显得很难看，所以你希望统计任意两个相邻木块颜色不同的着色方案。

法一：记搜：记f[i][1][2][3][4][5][last]表示考虑前i位，剩余12345桶油漆的种类分别有...种，上一次涂的是剩几块的油漆；

法二：

sum[i]表示cnt[i]的前缀和

设f[i][j]表示用了前i种颜色涂了sum[i]个块，其中有j对相邻同色块的方案数

考虑转移f[i][j]：

cnt[i + 1]分成a组，准备插入

b组插入到之前同色的之间

a-b组插空放不相邻

那么就是转移给f[i + 1][j - b + cnt[i + 1] - a] 方案数为f[i][j] * C[cnt[i + 1] - 1][a - 1] * C[j][b] * C[sum[i] + 1 - j][a - b]

$C[j][b]$就是插入到之前同色的之间的方案数（位置不同） $C[sum[i] + 1 - j][a - b]$就是相当于前面有sum[i]+1个位置，j个相邻块占据的位置不能放，a-b插入进去的方案数 ## 连边 有N个点（编号1到N）组成的无向图，已经为你连了M条边。请你再连K条边，使得所有的点的度数都是偶数。求有多少种连的方法。要求你连的K条边中不能有重边，但和已经连好的边可以重。不允许自环的存在。求连边的方法数。我们只关心它模10007的余数。 ~~复习一下乘法逆元的线性求解~~ 令f[i][j]表示加i条边，j个奇点的方案 $f[i][j]+=f[i-1][j-2]*C(n-j+2,2) f[i][j]+=f[i-1][j]*(n-j)*j f[i][j]+=f[i-1][j+2]*C(j+2,2)

还要减去重复的方案：

f[i][j]-=f[i-2][j]*(C(n,2)-(i-2))

这个剪去重复的方案非常有意思：

我们每次只去重最后加入的两条边；

因为是重边，所以奇点个数不变，我们枚举这两条重边，有C(n,2)种，其中i-2种已经在f[i-2][j]的状态中完成了去重，还剩下C(n,2)-(i-2)条边，我们会加入两次；

因为是有序的，转为无序的

f[i][j]/=i

边是无序的，我们加入时是有序的，所以要每次除以i；

多重集合的组合数

在 S 中任选 r 个元素的排列称为S的r排列，当r = n时，有公式 P(n; n1*a1, n2*a2, ..., nk*ak) = n! / (n1! * n2! * ...* nk!)

在 S 中任选 r 个元素的组合称为S的r组合，当r<=任意n_i时，有公式 C(n; n1*a1, n2*a2, ..., nk*ak) = C(k+r-1, r) = C(k+r-1,k-1)

证明：

我们只需要考虑这一个条件\sum \limits_{i=1}^kx_i=r；

相当于把r个球放到k个盒子里，盒子可以空的方案数；

如果r没有特殊的限制条件呢？也就是说r可以大于n_i；

容斥！强制选择过量的某个集合的元素；

环形染色问题

一个环形分成n块，有m种颜色的花可供选取，要求相邻区域颜色不能相同，共有多少种方法？

设n个花坛染色方法数为A_n

那么可分为两种情况

第一种

如果是n-1个花坛，共有A_{n-1}种染色方法，这时选取任意相邻的两个花坛，注意它们的颜色一定是不同的，

在它们的中间再添一个花坛，这个花坛有（m-2）种染色方法，此方案共(m-2)A_{n-1}种染色方法

第二种

如果是n-2个花坛，则共有A_{n-2}种染色方法，这时，任意选择一个花坛，将它拆分为两个，注意这两个颜色一定是相同的，此时共有n-1个花坛，然后再在这两个相同的花坛中添一个花坛，这个花坛有（m-1）种染色方法，此案共(m-1)A_{n-2}种染色方法

于是得到递推式

这是一个二阶常系数递推式，求通项过程暂略

最终求得通项公式为（排列与组合）环形染色问题

Catalan数

令h(0)=1，h(1)=1，Catalan数满足递归式：h(n) = h(0)*h(n-1) + h(1)*h(n-2) + ... + h(n-1)*h(0),(n>=2)

Nowcoder PJ2-D 合法括号序列

计数类问题，可以把各种产生不同的情况独立处理，然后乘起来得到答案

键盘上有左括号(，右括号)，和退格键-，共三个键。
牛牛希望按键n次，使得输入的字符串恰好一个合法的括号序列。
每按一次左括号(，字符串末尾追加一个左括号(
每按一次右括号)，字符串末尾追加一个右括号)
每按一次退格键-，会删掉字符串的最后一个字符，
特别的，如果字符串为空，牛牛也可以按退格，但是什么都不会发生。
答案对p取模

这个题可以分为两部分，

• 一部分是讨论最后合法括号序列的长度2k

• 二部分是有多少种输入他的方式

对于第一部分，是基本的卡特兰数。

对于第二部分，输入一个长度为2k的字符串，无论序列是什么，方案数是一定的。

也就是说方案数只和想输入的字符串长度有关，和具体是什么没关系。

设f[i][j]为按键i次，输入了长度为j的序列。

考虑转移：

在这种转移中，我们把填入什么括号视为同一种情况，因为最后留下的括号怎么填，是卡特兰数；

$f[i][0]=f[i-1][0]+2*f[i-1][1]$ 前者是在字符串为空的情况下再按一下空格； 最后枚举k，统计答案即可。 ## CF559C Gerald and Giant Chess 给定一张棋盘，有坏点（N<=2000），每次可以向下向右走，求左上角到右下角的方案数，取模； 现将左上角和右下角加入到“坏点”集合里，方便计算； 很明显我们要以坏点为关键点转移，设$f[i]$表示从左上角到达第i个坏点，不经过其他坏点的方案数； 使用了容斥原理； $f[i]=\text{从左上角到i的方案数}-f[j]\times \text{从j到i的方案数}

我们枚举路径上经过的第一个坏点是哪个，后面可以随意走，减去这些方案数；

拥有N个点的无向连通图个数，每个点不同

和上一题类似，容斥,枚举节点1所在的联通块的大小：

f[i]=2^{i\times (i-1)/2}-\sum \limits_{j \in [1,i-1]} C^{j-1}_{i-1}\times f[j]\times 2^{(i-j)\times (i-j-1)/2}

类似的，可以计算左侧n个点，右侧m个点的联通二分图个数；

How many of them

计算满足下列条件的无向连通图个数
1.由N个节点，每个节点有编号
2.割边不超过M条
3.没有自环和重边
N<=50

首先，割边最多有N-1条；如果把每个双连通分量看成一个节点，则所有双连通分量和割边构成一个树形结构；

围绕基准点构造一个整体！

设f(i,j)表示i个点j条割边的方案数，G(i,j,k)表示i个点j条割边k个联通块的方案数；

先来考虑j>0的情况：我们枚举1号点所在的点双的大小，删除之后的联通块个数

f(i,j)=\sum \limits_{k=1}^{i-1} f(k,0) \times C^{k-1}_{n-1} \times \sum \limits_{h=1}^{min(i-k,j)} G(i-k,j-h,h) \times k^h

最后k^h是因为，这剩下的h个联通块，每个可以和k个连边；

BZOJ 4403

给定三个正整数N、L和R，统计长度在1到N之间，元素大小都在L到R之间的单调不降序列的数量。

最开始想的时候，给球加了个数量限制，导致很难做，但是完全不用的，因为每种球都够选；

将每个位置放什么看作球，m个数看作盒子，由于可以不选，所以有m+1个盒子，于是就转化为了盒子与球

盒子与球·新

有m种球，每种球有无限个，取n次，最多能取多少种组合？（与顺序无关）

把每次的选择看成球，选择一个真实的球就相当于把虚拟的球放进相应编号的盒子，n球m盒可以空；

很强的转化：先把选择的球按编号排成一排（1...m），然后我们把它们分成m段，规定第一段对应的区间为第一种球，而每段可以空的方案数；

[JXOI2018]游戏

最终对答案有贡献的只有“独立的数”，也就是它不能被[l,r]中的任何一个数整除；统计独立的数，可以埃拉托色尼筛法O(N\log \log N)；对于一个排列最末尾的关键数字所在的位置即是它的检查时间。

接下来有很多证明方法，说两个：

第二个：神仙

问题转换为在n个数中随机取k个数，最末尾的数字的位置的期望乘以n的阶乘（即所有排列总数）。如果是期望，那么肯定是平均分布,可以得出位置的期望为k/(k+1)×(n+1)(因为位置从1开始数起)，则总答案即为k/(k+1)×((n+1)!)

组合数公式

1C_n^1+2C_n^2+3C_n^3+……+nC_n^n =n2^{n-1} 1^2C_n^1+2^2C_n^2+3^2C_n^3+……+n^2C _n^n =n(n+1)2^{n-2} (C_n^0)^2+(C_n^1)^2+(C_n^2)^2+……+(C _n^n)^2 = C_{2n}^n

对最后一个的证明：

严格N元树

计数类问题如果无法保证恰好...，不妨把状态改为至少...，然后前缀和相减即可

如果一棵树的所有非叶节点都恰好有n个儿子，那么我们称它为严格n元树。如果该树中最底层的节点深度为d（根的深度为0），那么我们称它为一棵深度为d的严格n元树。

设f[i]为深度小于等于i的n元树个数，则f[i]=f[i-1]^n+1，特殊的f[0]=1；

后面那个+1是统计1个点；然后f[d]-f[d-1]就是答案；

BBQ Hard

又一次弄混数据范围祭

将组合数C^n_{n+m}转化为方格图移动方案数很妙，然后利用坐标比较小，加上偏移量之后可以DP了；每次枚举第一象限的点，得到从其他所有点出发到这个点的方案数，减去自己到自己的方案数；

由于会枚举两次，所以要除以2；

杨辉三角矩形和

\sum_{i=0}^{a}\sum_{j=0}^{b} C_{i+j}^{i}=C_{a+b+1}^{a+1}-1

证明的话，画一个图，感觉一下；