基本反演推论对于\(|F|=n,|G|=m\)，要证明\(F[x]=\sum_\limits{i=0}^{+\infin}A[x,i]G[i]\iffG[x]=\sum_\limits{i=0}^{+\infin}B[x,i]F[i]\)。\(F\)为\(G\)的前缀和，\(F[x]=\sum_\limits{i=0}^{+\infin}[i\leqx]G[i],G[x]=\sum_\limits{i=0}^{\in

两年前学的东西，今天补一下笔记。Intro考虑\(n\)个有标号的元素。令\(f_n\)表示恰好\(n\)个元素满足条件（这里的条件取决于具体问题）的方案数，\(g_n\)表示指定\(n\)个元素满足条件的方案数。那么显然有\[g_n=\sum_{i=n}^mC_i^nf_i\]比如说，对于\(f_i\)，可以选出\(n

这是国庆作业。很巧的是我的二项式定理学习笔记正好是去年国庆时写的。因为是发视频作业，所以这算是稿子。在中国，成书于1世纪的《九章算术》提出了世界上最早的多位正整数开平方、开立方的一般程序。11世纪中叶，贾宪在其《释锁算书》中给出了“开方作法本原图”，满足了三次以上开

T1构造字符串签到题注意到\(n\)和\(m\)较小，直接扫一遍用并查集维护他所描述的情况，并将不同的位置记录下来，若存在不同的位置属于同一个集合则不可能构成，否则贪心从前往后取mex即可。时间复杂度\(O(nm\alpha(n))\)。T2寻宝签到题首先先用并查集将大联通块缩点，注意到

基础组合数学组合数\[\binom{n}{m}=\frac{n^{\underline{m}}}{m!}\]性质加法恒等式:\[\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}\]提取吸收恒等式：\[\binom{n}{m}=\frac{n}{m}\binom{n-1}{m-1}\]二项式定理\[(a+b)^n=\sum_{k=0}^\inf

前言万字长文！这里有我的一些思考和领会，网络上的教程都太潦草了。并且我发现了新的反演公式！概述二项式反演用于转化两个具有特殊关系的函数\(f\)和\(g\)，从而方便求解问题。一般来说，直接计算恰好满足\(n\)个限制的答案不好求，但是可以计算出“至少”/“至多”满足\(n\)

【2】容斥与二项式反演1.1容斥原理容斥原理基于的是下面的恒等式：\[\sum\limits_{i=0}^n\dbinom{n}{i}(-1)^i=0^n=[n=0]\]这个式子有什么意义呢？我们考虑一个长度为\(N\)的序列，并且要求其中每个元素都满足某个限制，计算满足这个条件的序列数量。每个元素都满足限制\(\Leftri

OSUOSUAnotherOSUyetAnotherOSUyetyetAnotherOSUOSU的题目是这样的：有一些相邻的块，给定每一个块的联通概率，每个连通块对答案有\(size^{3}\)的贡献，求总期望关于此题我曾写过题解此处此类题的关键之处在于，当我们设计了一个线性状态\(f_{i}\)之后，假如我们基于拼接

二项式定理$\quad\quad\quad(x+y)^n=\sum_{k=0}^{n}{n\choosek}x^{n-k}y^k$证明\(\quad(x+y)^n=(x+y)*(x+y)*(x+y)*...\)我们考虑多项式乘法\((a+b)*(a+b)=a*a+a*b+b*a+b*b\)于是我们枚举每个因子相乘，可以发现\((x+y)^n\)每个括号里的\(x\)和\(y\)最多只能选

目录引入正题延伸引入首先有一个广为人知的结论：\[(a+b)^2=a^2+2ab+b^2\]那么，如何求\((a+b)^3\)呢？手算，如下：\[\begin{aligned}(a+b)^3&=(a+b)\times(a+b)^2\\&=(a+b)\times(a^2+2ab+b^2)\\&=[a\times(a^2+2ab+b^2)]+[b\times(a^2+2ab+b^2)]\\&=(a^3+2a^2b+ab^

8.16日集训倒数第\(7\)天唉，不知不觉间在ssy中学的暑假集训就要结束了，只剩下一周的时间了，然而byn和yzh还有bao学姐\(21\)号就要走了，暑假就要过去了....今天模拟赛的第二题很有意思，涉及到了许多的数学知识，正好来恶补一下：浅谈反演原理和二项式反演首先来说说什么是反演(inversio

二项式系数  二项式定理证明过程 (x+y)^n=(x+y)(x+y)(x+y)........(x+y)我们先展开式子，得出以上等式。为了方便，我们以n=3举例(x+y)^3=(x+y)(x+y)(x+y)对于每一个因式（即每一个（x+y）），都可以选择x或者y和其他的因式（即其他的（x+y））也选出x或者y相乘，然

卡特兰数常见公式：不是很懂。\[H_n=C_{2n}^n-C_{2n}^{n-1}\]应用：折线计数。第二类斯特林数在小球与盒子那道模板题中见到的，表示表示将\(n\)个两两不同的元素，划分为\(k\)个互不区分的非空子集的方案数。递推式：\[\operatorname{S2}_{i,j}=j\times\operatorname{S2}_{i-

文章目录待定系数法应用示例1.多项式除法2.分式化简3.数列通项公式总结递归数列特征方程特征根的求解通项公式的求解示例错位相减，差分错位相减法差分的应用结合理解韦达定理二项式定理二项式定理的通项公式二项式系数的性质应用示例一元二次求解1.因式分解

排列组合：公式及推导引入定义：排列：从指定个数的元素中取出指定个数的元素进行排序；(考虑元素的顺序)组合：从给定个数的元素中仅仅取出指定个数的元素；(不考虑元素的顺序)加法&乘法原理加法原理：完成一个工程可以有\(n\)类办法，\(a_i(i\in[1,n])\)代表第\(i\)类方法的数目。则

在写状压dp时，经常会见到如下句子：for(inti=0;i<(1<<n);i++){ for(intj=i;j!=0;j=(j-1)&i){ }}时间复杂度证明如下：单个\(x\)枚举子集复杂度易证(设\(y=log_2(x)\))：\[∑_{i=0}^{y}C^i_y\]使用二项式定理：\[(a+1)^n=∑_{i=0}^{n}C_n^i~a^i\]将上面的\(a\)

序（感谢9G对本博客证明的大力支持）前置知识1：排列组合2：多步容斥\[\dbinom{n}{m}=\binom{n}{n-m}=\mathrm{C}_n^m=\mathrm{C}_n^{n-m}\]\[\dbinom{n}{m}*\binom{m}{s}=\dbinom{n}{s}*\binom{n-s}{n-m}\]\[\dbinom{n}{x-1}+\binom{n}{x}=\dbinom{n+1}{x}\]证明：\(\dbinom{n}{x

二项式定理：\[(a+b)^n=\sum_{i=0}^{n}\binom{n}{i}a^ib^{n-i}\]很好理解。我们经常会使用的式子：\[(1+x)^n=\sum_{i=0}^{n}x^i\binom{n}{i}\]容斥定理：\[\begin{split}\left|\bigcup_{i=1}^{n}S_i\right|=&\sum_{i}|S_i|-\sum_{i<j}|S_i\capS_j|+\sum_{i<j&

https://www.becoder.com.cn/contest/5400「BZOJ2863」愤怒的元首题目就是求\(n\)个点DAG的数量。设\(dp_i\)表示\(i\)个点的DAG数量。首先DAG一定存在出度为\(0\)的点，其次删去出度为\(0\)的点，仍构成一个DAG。所以我们可以枚举删去的数量，从而划分子问题。

https://www.becoder.com.cn/contest/5400「BZOJ2863」愤怒的元首题目就是求\(n\)个点DAG的数量。设\(dp_i\)表示\(i\)个点的DAG数量。首先DAG一定存在出度为\(0\)的点，其次删去出度为\(0\)的点，仍构成一个DAG。所以我们可以枚举删去的数量，从而划分子问题。

二项式定理\[(x+y)^{n}=\sum_{i=0}^{n}{n\choosei}x^{i}y^{n-i}\]多元二项式定理：\[(x_{1}+\cdots+x_{k})^{n}=\sum_{\summ_{i}=n}{n\choosem_{1},m_{2},\cdots,m_{k}}x_{1}^{m_{1}}x_{2}^{m_{2}}\cdotsx_{k}^{m_{k}}\]广义二项式定理：\[(x+y)^{\alpha}=\sum_{i=0}^{\in

篇幅有限，仅记录公式及极简证明。定义\[\begin{aligned}&f(n)=\sum_{i=0}^n(-1)^i{n\choosei}g(i)\Leftrightarrowg(n)=\sum_{i=0}^n(-1)^i{n\choosei}f(i)&(1)\\&f(n)=\sum_{i=0}^n{n\choosei}g(i)\Leftrightarrowg(n)=\sum_{i=0}^n(-1)^{n+i}{n\cho

二项式反演简介二项式反演可以用来解决一些计数问题，是连接至少/至多与恰好两类函数的桥梁。形式一\[f(n)=\sum_{i=0}^n(-1)^i\binom{n}{i}g(i)\\g(n)=\sum_{i=0}^n(-1)^i\binom{n}{i}f(i)\]证明代\(g(n)\)入第一条式子。\[\begin{aligned}f(n)&=\sum

这是一道*1900的黑。考虑枚举\(m\)，将\(<\fracm2\)和\(\ge\fracm2\)的数分开讨论。考虑相邻两个数\(a,b\(a>b)\)分别在\(\fracm2\)的两侧，则有\(b\gem-a\)。考虑将所有数按某种方法从小到大排序，以\(\min(x,m-x)\)为第一关键字，\(-x\)为第二关键字，则排列中

题意简述有\(m\)张牌，其中有一张是王牌。你现在可以洗\(n\)次牌（每种牌堆序列等概率出现），然后查看牌堆顶的第一张牌。设\(x\)为\(n\)次洗牌中第一张牌是王牌的次数，则得分为\(x^k\)。求得分的期望值对\(998244353\)取模的值。\(1\len,m<998244353,k\le5000\)分析将