ATBAB设\(f_{i,0/1}\)表示\(i\)子树DFS序奇/偶位置和的最大值，首先如果\(i\)所有孩子的子树大小都是偶数，那访问这些孩子的顺序就无所谓了，否则考虑以\(i\)的至少一个大小为奇数的孩子为分界，对所有大小为偶数的孩子\(v\)，把\(f_{v,0}\)更大的\(v\)、\(f_{v,1}\)

闲话推歌：Empurpleby春卷饭feat.初音未来虽然是商曲吧，但是确实仙品这种破题方法确实很巧妙，从发色出发，分解成红+蓝再寻找其抽象的指代意但不停留于此，而是接着探讨更深刻的问题（例如童年、家庭、控制过程中仍然是大量的隐喻和意象。我得到的结论就是，紫化不是无法变成红色的妥

前话很早就想给随机游走类问题做个总结了，以后又想到一题不定期更新。2024.6.22题目描述一维空间内，前进一步，后退一步，原地不同概率均为\(\cfrac{1}{3}\)，\(0\)点后退后还是\(0\)点。求从\(0\)点走到右端点\(n\)的期望步数。解决套路化记\(f[i]\)表示从\(i\)走到\(

快速变换设原多项式为\(F(x)=\sum_{i\in[0,n)}a_ix^i\)，其中\(n=2^k,k\in\mathbbZ^+\)。我们要求\(\foralli\in[0,n),\hata_i=F(t_i)\)，其中\(t\)是一个长度为\(n\)且两两互不相同的序列。显然\(F\)可以被一组\(\hata,t\)唯一确定，即点值表示

TheMethodofSnakeOil进行组合求和的蛇油法。确定求和所依赖的自由变量，例如\(n\)。为您正在处理的求和命名；称之为\(f_n\)。让\(F(x)\)成为\(f(n)\)的生成函数，即您想要求和的和。将和乘以\(x^n\)，然后对\(n\)求和。您的生成函数现在表示为对\(n\)的双重求和，以及

定义第一类斯特林数\[c(n,k)=|s(n,k)|=(-1)^{n-k}s(n,k)\]给出定义：\[x^{\barn}=\sum_{k=0}^kc(n,k)x^k\\x^{\underlinen}=\sum_{k=0}^ns(n,k)x^k=\sum_{k=0}^n(-1)^{n-k}c(n,k)x^k\]通常把\(c(n,k)\)称为无标号第一类斯特林数，\(s(n,k)\)称为有标号第一类斯特林数。

篇幅有限，仅记录公式及极简证明。定义\[\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

一道非常厉害的题目。题意求：\[\sum_{i=0}^{m}c(n,i)\modp\]其中\(c(n,i)\)为无标号第一类斯特林数，且有\(n,m\le10^{18},p\le10^6\)。Sol考虑一个性质：\[x^{\overlinep}\equivx^p-x\modp\]证明比较简单，考虑费马小定理，\(x^p\equivx\modp\)。而\(x,x+1,\cdots,x+

可能不全，老文章在这什么是通解，我们知道二元一次方程，是如果只有一个式子，那么解会有无数个，而通解就是指让我们只找到一个解就可以推出其他所有解的式子。注意以下变量都为整数。知道了定义下面就是推式子了，首先设\(x,y\)是\(ax+by=\gcd(a,b)\)的一个解，那么有\[y=\le

二项式反演简介二项式反演可以用来解决一些计数问题，是连接至少/至多与恰好两类函数的桥梁。形式一\[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

T1证明\(\negA\rightarrowB,\negA\rightarrow\negB\vdashA\)可用定理：\(\vdash(\negA\rightarrowA)\rightarrowA\)Proof\[\begin{aligned}A_1:\quad&\negA\rightarrowB&\in\Gamma\\A_2:\quad&\negA\rightarrow

矩阵树定理学习笔记真的，我这辈子都没有想过行列式还能用到这种地方。定义图的关联矩阵对于一张有\(n\)个点、\(m\)条边的图（对于无向图，可以随便定义边的方向，因为相反的边只需要将对应列乘以\(-1\)即可），我们定义其关联矩阵\(M\)满足：\[M_{i,j}=\left\{\begin{matrix}1&e_j

朗之万动力学原理简介本文的主要内容是基于以下教程：TutorialonDiffusionModelsforImagingandVisionhttps://arxiv.org/abs/2403.18103此教程写的非常好，非常推荐大家学习。教程的语言风格也很亲切，时不时地蹦出诸如“这是地球人能想出来的公式？”这样的话，为你枯燥的学习

$\quad$实在蒟蒻，不看题解就只能对着电脑发呆，想了一个脚指头都能想出来的\(O(n\timesn!)\)的暴力做法。$\quad$也是看了好多题解才大概明白式子推法。$\quad$先考虑枚举每个可能的视野长度，那么就会有;\begin{aligned}ans&=\sum_{i=1}^{n}{i\timesP(i)}\\&=\sum_{

莫比乌斯反演速通前言由于请假错过了讲课，所以莫反是我第一个需要自学的难度不小的数学知识。自学的过程的狼狈的，旁边也曾是自学的czn告诉我如果学会“狄利克雷卷积”就可以对“莫比乌斯反演”的理解进行“降维打击”。他还十分热心地带着我速通了一遍狄卷与莫反。一知半解，就

目录目录前言1.热力学第一定律2.理想气体的热容3.理想气体四种过程的计算前言其实是想直接开始写热力学基础的内容的，但是我发现这部分非常需要前置的气体动理论的支撑，因此先写完了气体动理论再开始写热力学基础相关内容。鉴于这部分的内容量比较大，我也不打算再分多篇了，就直

这一章主要讲解各种组合恒等式。但是事实上，有很大一部分都能用有限微积分、OGF、EGF之类的武器轻松搞定。组合恒等式组合数定义朴素定义：\[\binomnm=\dfrac{n!}{m!(n-m)!}\]下降幂定义：\[\binomnm=\dfrac{n^{\underlinem}}{m!}\]组合数递推式（Pascal'sIdenti

P10227[COCI2023/2024#3]SlučajnaCesta题解知识点期望DP，树形（换根）DP，组合数学。题意分析一棵树，每个点都有点权，每一条边的方向分布都是等概率的，问从每个点出发，有路走就一直走的情况下，所途径的点的权值总和的期望值。思路分析这明显是一个树形DP，且需要变成换根DP

阅读前需深剖析分系列是记录我个人的做题思路，实现过程的全面分析，存在内容可靠、思路健全、分析到位、试错纠错等优于一般题解的特征，其中，Quest部分表示探索问题，我会在此提出做题时的想法、问题，并在内容中得到解决，因此建议从上到下按序浏览，以防出现思路断层，内容不衔接的情况，感谢理

无滑滚动假设有拉力\(F\)以及摩擦力\(F_f\)，圆柱体无滑滚动（\(a=\alphaR\)），下面讨论其动能变化由质心运动定理：\[F-F_f=ma\]由刚体定轴转动的转动定理：\[(F+F_f)R=I_c\alpha\]可得：\[a=\frac{2F}{m+\frac{I_c}{R^2}}\]故刚体动能为：\[\begin{aligned}E_k&=\frac{1}{2}mv^2+\f

基本操作集合并卷积集合幂卷积定义为：给定两个集合幂级数\(F,G\)，计算集合幂级数\(H\)满足：\[\begin{aligned}h_S=\sum_{L\subset2^U}\sum_{R\subset2^U}[L\cupR=S]f_Lg_R\end{aligned}\]我们考虑用类似于FFT的方式，把\(f,g\)按某种线性变换后，然后把问题变成点乘。

多项式乘法存在多项式\(F(z)=\sum_{i=0}^na_iz^i,G(z)=\sum_{i=0}^mb_iz^i\)，我们定义多项式乘法：\[F(z)*G(z)=\sum_i\sum_ja_ib_jz^{i+j}\]多项式的点值表达一个\(n\)次函数可以用平面上的\(n+1\)个点来表达。所以我们可以把一个\(n\)次多项式从系数表达转化成\(n+

BinomialSum如果我们有一个微分有限函数\(F(z)\)，还有另外一个生成函数\(G(z)\)，一个数列\(a\)，如果我们能对\(k\in[0,n]\)的每一个\(k\)快速求出\(G^k(z)\)的前\(n\)项系数带权和，即\[b_k=\sum_{i=0}^na_i[z^i]G^k(z)\]那么我们可以在\(\Theta(n)\)的时间复杂度内

二项式系数更完整的思考过程以及代数推理过程都可以看数学书，所以我尽量给每个式子都赋予组合意义。因为在有足够强的代数推理能力之前，没有组合意义往往是困难的。恒等式赋予组合意义往往都是左边右边分开找意义。常见公式：\[\begin{aligned}\binom{n}{k}&=\binom{n}{n-k}\en

生成函数我们可以把生成函数看作是代数对象，其形式上的处理使得人们可以通过代数手段计算一个计数问题。通常我们默认级数是收敛的。(主要原因在于代数手段往往是需要保证收敛的)本文章不涉及多项式题目（交给考拉）普通生成函数的定义为：\[\displaystyle\sum_{n}a_nx^n\]常见的