自学笔记类杂谈
又能隐隐约约深深浅浅地 在黑夜中看到 飘渺似无凭的 向阳花 —— 庸人之夏
——————————————————————————————————————————
组合基础TRICK
Cnm=C(n,n−m)C_n^m=C(n,n-m)Cnm =C(n,n−m)
Cnm=C(n−1,m)+C(n−1,m−1)C_n^m=C(n-1,m)+C(n-1,m-1)Cnm =C(n−1,m)+C(n−1,m−1)（从n个数中选出m个数，假设某一个数我没选，那么就要从剩下的n-1个数中选出m个数；假设某一个数我选了，那么就要从剩余的n-1个数中选出m-1个数）
很多组合数的基础公式和技巧都是可以用杨辉三角推出来的。（二项式定理，2n2^n2n，……）
组合数也经常被称为二项式系数。
还有一些二项式定理相关的（比如奇正偶负的情况下，杨辉三角一行加起来等于零。全正的情况下，加起来等于2n2^n2n）关于它们的证明，都是可以直接有杨辉三角的模型一点点推/摸索出来的。
隔板法（插空法）
m这个数切割成n个数的和：在n-1个空位中，放m个板子
也就是C(n−1,m)C(n-1,m)C(n−1,m)
m颗糖果分给n个小朋友（m分割成n个部分）
n个部分相加等于m
如何使用隔板法？ 确定序列 or 拆分序列 -> 隔板法
快速幂
这玩意儿我一万年前就见过了。但是至今其实不是特别理解。
https://www.luogu.com.cn/problem/P1226
所以现在来写一下思路好了。
我比较喜欢的做法是把bbb二进制拆分掉：ai0+ai1+....+aix=aba^{i_0}+a^{i_1}+....+a^{i_x}=a^bai0 +ai1 +....+aix =ab
bbb可以拆分成一堆二的次幂相乘（详见二进制）
所以我们可以拥有这样一段代码：
来摸一个小例子，不然可能会有一点Bug。
样例：2 10 9
我们忽略mod
10=23+2110=2^3+2^110=23+21
210=223∗221=28∗222^{10}=2^{2^3}*2^{2^1}=2^8*2^2210=223∗221=28∗22
然后按照代码的形式去跑一遍整个过程：
1. a=a∗a=2∗2=4=22a=a*a=2*2=4=2^2a=a∗a=2∗2=4=22
2. ans=ans∗a=4ans=ans*a=4ans=ans∗a=4 & a=a∗a=4∗4=22∗22=24a=a*a=4*4=2^2*2^2=2^4a=a∗a=4∗4=22∗22=24
3. a=a∗a=24∗24=28a=a*a=2^4*2^4=2^8a=a∗a=24∗24=28
4. ans=ans∗a=22∗28=210ans=ans*a=2^2*2^8=2^{10}ans=ans∗a=22∗28=210
隔板法相关运用
https://www.luogu.com.cn/problem/P6475
这是一个很复杂的题目。
我们考虑将题目分段思考。
先抛弃“第x个数和第y个数相等”的部分。简单地思考“前n个数不下降”和“后n个数不上升”如何去计算有多少种方案。
考虑另一件事：其实我们可以把”不下降“也抛掉。因为我们可以直接考虑要在mmm个数中选出nnn个数的不同方案，假装它们后面会自己排序（而我们不需要考虑它的顺序）
而且注意到mmm个数是可以重复选择的，那一共有多少种方法呢？
此时我们可以牵强地联系一下隔板法：比如我们有一个数列：[1,1,2,2,2,3]
那要放置的板就是：[1,1 | 2,2,2 | 3] 不过需要注意：我们不一定一定要在这个序列中塞上m个数（虽然我们有m个选择）
也就是说，我们接受空盒状态，那么总选择数就从C(n−1,m−1)C(n-1,m-1)C(n−1,m−1)变成了C(n+m−1,m−1)C(n+m-1,m-1)C(n+m−1,m−1)（因为板和板也可以塞在一起）
n个位置的数不下降和不上升其实是相同的处理方式。因为顺序本身对组合来说并不重要。
所以接下来我们要考虑第x个数和第y个数相等的情况如何处理。
这里我们需要分类讨论。
1.第x个数和第y个数都在前n个数中
2.第x个数和第y个数都在后n个数中
3.第x个数和第y个数一个在前n个数里，一个在后n个数里
不难发现第一种情况和第二种情况是相似的。
所以我们打包解决。
（备注：高度是可以枚举的）
已知序列要求不下降。也就是说，从第x个数到第y个数必须全部相等。
此时序列分成三个部分：[1,x) [x,y] (y,n]
[x,y]是固定的，[1,x)和(y,n]可以重用大区间方案书的计算方法。毕竟通用。
（哦哦哦。这里需要注意的一个点是：需要把值域更改，因为理论上而言区间从左到有右拼接需要是有序的）
最后的方案书就是将前面区间的方案数乘上后面区间的方案数。
最后我们来看方案三。
我们需要考虑第x个位置为h，第y个位置为h的方案数。
这边将数值固定，也就是将x前后和y前后的区间的值域固定。
哦。也就是说，三种情况其实差不多。
只是最后一种方案需要重复两次操作。
终于把代码打完了。先把它放置在这里，然后我来逐行讲解。
首先这道题目的各种边界很难调试。要调可能也只有瞪眼。
其次注意for循环二进制方法的快速幂如果边界设置不对可能会炸的你样例都过不去。
还有就是各种mod每一次乘法加法都要加mod，不然你也会挂分。
这道题确实有点吃操作。
矩阵
矩阵与矩阵的乘法：只有一个矩阵的列(n*m)和另一个矩阵的行(m *k)相同才可以相乘。6
则它们可以相乘并得到一个n∗kn*kn∗k的矩阵C。
将方程问题转化成矩阵问题再解决。
快速幂2
我发现我的第一个版本快速幂会炸。
所以我打算再学一种新的！
其实原理是一样的，但是其实现方式并不相同。
for循环你很有可能会因为边界问题而挂分，我们要杜绝这种可能。
今天我们学的比较重要的是：组合->插板法->插板法的变式
然后来写点作业：
这玩意儿。一眼卡特兰。我不会告诉你我已经忘记了
再往后一看：答案小于七百位。豁。高精度。不做。
跳一题，看下一题。
想到的初步思路是：挨个枚举第一个一的位置。先枚举第一个1的位置，看如果1在第i位上会有多少种方案，如果方案小于目前所需，那就i++，否则就去枚举第二个1的位置……
另：如何不超过long long去计算n,m<=40的组合数：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
华丽的红房间 发霉的旧唱片 没必要听个遍 掉了漆的播放键
