更好的阅读体验update2024-11-1211:25修改了一些格式错误且增加了二项式反演的例题2024-11-1214:33改进了二项式反演的证明基础知识一、加法原理完成某个工作有\(n\)类办法，第\(i\)类办法有\(a_i\)种，则完成此工作的方案数有\(\sum\limits_{i=1}^na_i\)种。二

基本反演推论对于\(|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

反演“反演”的本质:两个函数之间的双向关系。我们通常可以用矩阵来描述这种关系。\[F=G*A\\F*A^T=G\]\(A\)即为关系矩阵。所谓反演就是关系矩阵的逆。\[B=A^T\\F*B=F*A^T=G\]利用关系矩阵，我们就可以实现两个矩阵（函数）的来回变化。二项式反演：形式一：\[A[n,i]=(-1)

多校A层冲刺NOIP2024模拟赛18\(T1\)A.选彩笔（rgb）\(100pts/100pts\)观察到\(0\ler,g,b\le255\)且答案具有单调性，故考虑二分答案。将\(r,g,b\)分别抽象成三维坐标下的\(x,y,z\)。设当前二分出的答案为\(mid\)，由调整法分析可知若存在一个边长为\(mid\)的

TeamWork题意：求\(\sum_{i=1}^n\dbinom{n}{i}i^k\)\(n<=1e9,k<=5e3\)推式子\[\begin{aligned}记f_{n,k}&=\sum_{i=1}^n\dbinom{n}{i}i^k\\&=\sum_{i=1}^n\left[\dbinom{n-1}{i-1}+\dbinom{n-1}{i}\right]i^k\\&=\sum_{i=1}^n\d

NOIP2024集训Day37DPA.[CQOI2011]放棋子设\(f_{i,j,k}\)表示前\(k\)种棋子放了任意\(i\)行、\(j\)列。决策是：在哪些位置填同种颜色的棋子。于是美剧上一个状态的\(i,j\)（表示为\(l,r\)），上一状态\(k_1=k-1\)。设\(g_{i,j,k}\)表示\(k\)个同种颜色的

欢迎收看\(T3\)爆标解法！额，在此感谢一下Jijidawang的帮助，式子从\(n^2\)到\(nk\)基本都是他做的，（没办法，我太菜了。。。）节点\(x\)在其子树大小为\(i\)时的方案数为\(\dbinom{n-i-1}{x-2}\),然后我们就有了\(n^2\)解法，设方案数为\(cnt_x\)\[\sum_{x=1}^{n}a_x\frac{

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

除了组合数、卡特兰数之外，最重要的一类特殊数便是斯特林数。1.1第二类斯特林数斯特林数通常有两种，分别为第一类斯特林数和第二类斯特林数，后者通常更为重要。与组合数类似，第二类斯特林数也有自己的符号$\begin{Bmatrix}n\m\end{Bmatrix}$，其含义为把\(n\)个不同的数划分到

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

【1】组合数学基础我们用\(\dbinom{n}{m}\)代表组合数，其含义为从\(n\)个物体中选出\(m\)个的方案数，也可以记为\(C_{n}^m\)。记\(n\)的阶乘为\(\prod\limits_{i=1}^ni\)，记为\(n!\)。记\(n\)的\(m\)次下降幂为\(\prod\limits_{i=0}^{m-1}(n-i)=\frac{n!}{(n-m)!}

题意给定\(S\in\{(,),?\}\)。定义深度为括号嵌套的子序列的最大长度除以\(2\)。求出将\(?\)替换为括号的所有括号串的深度之和，对\(998244353\)取模。\(n\le10^6\)。Sol考虑如何把每次贡献只计算一次。不难想到在括号的中心点计算。可以发现，若当前左右括号

插板法\(n\)个无标号物品分成\(m\)个有标号组。非空：\[\dbinom{n-1}{m-1}\]空：\[\dbinom{n+m-1}{m-1}\]构造一一对应的转化：现有两个集合\(A,B\)。如果所有\(A\)中的元素都能够映射到\(B\)中，则\(|A|\le|B|\)；反之，如果\(B\)能映射到\(A\)，则\(|B|\le|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

一、鸽巢原理1.鸽巢原理将\((\sum\limits_{i=1}^n{p_i})-n+1\)放入\(n\)个盒子，一定存在一个盒子\(i\)，使得第\(i\)个盒子至少装了\(p_i\)个物品。练习一有十个数\(a_1,a_2\dotsa_{10}\)满足\(\forall_{1\leqi\leq10}{1\leqa_i\leq60}\)，证明能够从\(a_i\)中挑

基础知识一、加法原理完成某个工作有\(n\)类办法，第\(i\)类办法有\(a_i\)种，则完成此工作的方案数有\(\sum\limits_{i=1}^na_i\)种。二、乘法原理完成某个工作有\(n\)个步骤，第\(i\)个步骤有\(b_i\)种，则完成此工作的方案数有\(\prod\limits_{i=1}^nb_i\)种。

calcbysmallbasic前言拜谢smallbasic，出的神题，故写题解以记之。题解考虑各个数都在各自的范围内随机取值，并且可以是实数，这就很困难。我们可以将其拆开，得：设\(X=\sum\lfloorx_i\rfloor,Y=\lfloor\sum(x_i)\rfloor\)。\[(X+Y)^k=\sum_{i=0}^k\dbino

感觉这几个东西挺常用，记录一下吧。1.卡特兰数假如我们定义\(C_n\)表示第\(n\)个卡特兰数。然后我们就有一下几个式子。\(C_n=\dfrac{\dbinom{2n}{n}}{n+1}\)\(C_n=\begin{cases}\sum^n_{i=1}H_{i-1}H_{n-i}\\n\ge2\\1\end{cases}\)\(C_n=\dbin

组合数学基本概念\(a^{\underlinem}\)表示\(a\)的\(m\)次下降幂。\(a^{\overlinem}\)表示\(a\)的\(m\)次上升幂。递推式\[{n\choosem}={n-1\choosem}+{n-1\choosem-1}\\\]证明：从组合意义上推导，在n个人中选m个相当于单独考虑最后一人，若他要选，则为

ARC160D直接考虑从\(A\)变为全零数列不太好做，考虑将问题转化为从全零数列通过两种操作可以得到的\(A\)数列的个数。发现只要满足每个区间的加一次数\(\lek\)就能保证不同操作序列得到数列的唯一性，这个很好感性理解。于是题目转化成统计序列\(b_{1\sim2n-k+1}\)的个数，

$\large1.$容斥原理\[f(n)=\sum_{i=0}^n\dbinom{n}{i}g(i)\Leftrightarrowg(n)=\sum_{i=0}^n(-1)^{n-i}\dbinom{n}{i}f(i)\]$\largef$表示至多,\(\largeg\)表示恰好\[f(n)=\sum_{i=n}^m\dbinom{i}{n}g(i)\Leftrightarrowg(n)=\sum_{i

\(C^m_n\)由车夫乙发明，作用无需多说。是组合数学中的常用工具，组合意义为从\(n\)个物品中选\(m\)个的方案数。注：为了简便，\(C^m_n\)有时写作\(\dbinom{n}{m}\)。\(\begin{aligned}\dbinom{n}{m}=&\dfrac{n!}{m!(n-m)!}\\=&\dbinom{n-1}{m-1}+\dbinom{n-1}{m}\\=&\dfrac

题意简述给定\(n,x,y\)，定义序列\(\{a_n\}\)合法当且仅当\(\sum_{i=1}^na_i=x\)且\(\operatorname{or}_{i=1}^n=y\)，你需要求出\(\oplus_{a\\text{is}\\text{valid}}\oplus_{i=1}^na_i\)的值。\(n<2^{40},x<2^{60},y<2^{20}\)。分析第一步：先做一波非常重要的分析答

性质1以下组合恒等式成立:\(1\).\(\dbinom{n}{k}=\dbinom{n}{n-k}\).\(2\).\(\dbinom{n}{k}=\dbinom{n-1}{k}+\dbinom{n-1}{k-1}\).\(3\).\(\dbinom{n}{k}=\dfrac{n}{k}\dbinom{n-1}{k-1}\).证明:虽然可以代入组合数公式\(\dbinom{n}{k}=\dfrac{n!}{k!(n-k)!}\)暴力验