组合恒等式

$\binom{n}{m}=\binom{n}{n-m}$

$\sum_{i}\binom{n}{i}=2^n$

$\sum_{i}\binom{n}{m}[2|i]=2^{n-1}$

$\binom{n+m+1}{m}=\sum_i\binom{n+i}{n}$

等式右边是走到第n列所有小于m的点的方案数

而左边是走到(n+1,m)的方案数

$\sum_{i=m}^n\binom{i}{m}=\sum_{i=0}^{n-m}\binom{m+i}{m}=\binom{m+n-m+1}{n-m}=\binom{n+1}{n-m}=\binom{n+1}{m+1}$

$\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k}$

先选m再选k和先选k再选m-k一样

$\sum_{i=0}^k\binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k}$

考虑组合意义,左边n个选出了i个,右边m个选出了k-i个并对于i求和

所以在相当于在n+m个一下选出k个

自然数幂之和

$S_{n,k}=\sum_i^n i^k$ S是关于n的k+1次多项式

证明:利用归纳法和二项式定理展开

拉格朗日插值

$\sum_{i=0}^k y_i \prod_{i!=j} \frac{x-x_j}{x_i-x_j}$

如果我们有k+1个点值就能求出这个多项式插值形式

如果我们选的点值是连续的一段整数

$\sum_{i=0}^k y_i \prod_{i!=j} \frac{x-x_j}{x_i-x_j}$

对于分子,显然是两个阶乘相乘

对于分母,显然是一个前缀的阶乘和一个后缀的阶乘相乘

模数必须大于n的质数

斯特林数,分第一类第二类

第一类实际意义是分成一些轮换

第二类是分成一些集合

$S{n}{m}$

第一类递推:

$s{n,m}=s{n-1,m-1}+s{n-1,m}*{n-1}$插在哪一个数字后面

第二类递推

$s{n,m}=s{n-1,m-1}+s{n-1,m}*m$插在那个集合

第二类通项:

$s{n,m}=\frac{1}{m!}\sum_i^m(-1)^i\binom{m}{i}(m-i)^{n}$

第一类用途

$n^{下降幂}=\sum_{i=0}^k (-1)^{k-i}S1{k,i}n^i$

可以变成通常幂*第一类斯特林qwq

当$i=k$时有个$n^k$

对n西格玛

然后对下降幂用组合数和阶乘表示

得到:()_qwq表示下降幂

$S_k{n}=\frac{(n+1)^{(k+1)_{qwq}}}{k+1}-\sum_{j=0}^{k-1}(-1)^{k-j}S{k}{j}S_j{n}$

$Ok^2$可以求出这个$S_0~S_k$

你会发现对于模数没有要求,因为前面那个分式分子一定有一项可以搞掉分母qwq

伯努利数

生成函数定义

$\frac{x}{e^x-1}=\sum_{i=0}^{\inf}\frac{B_i}{i!}x^i$

伯努利多项式

$\sum_{i=0}^{\inf} \frac{\beta_i(t)}{i!}x^i=\frac{x}{e^x-1}e^{tx}$

$\beta_i(t)$是一个多项式

带入并展开化简可得

$\beta_i(t)=\sum_{k=0}^n\binom{n}{k}B_{n-k}t^k$

然后我们炫酷的构造一个做差的形式,然后并带入上式

得到:

$S_k{n}=\frac{1}{k+1}\sum_{i=0}^k\binom{k+1}{i}(n+1)^iB_{k+1-i}$

然后你妹的可以生成函数搞搞伯努利数的求法.....

构造$B=\sum_i\frac{B_i}{i!}x^i$

$A=\sum_n\frac{x^i}{(n+1)!}$

$B=\frac{1}{A+1}$

多项式求逆即可做到$O(klogk)$

啊这QAQAQ

模数要是好质数才行.....

T1:

偶回文串答案显然是10^{n/2},因为一定是等的

4k+1类型数

$2(x_1+x_3..+x_{2k-1})+x_{2k+1}=2(x_2+x_4...x_{2k})$

$x_1+x_2+x_3...x_k=n$

$0<=x_i<=9$

直接可以容斥

枚举至少i个大于等于10都减去10

$y_1+y_2....y_k=n-10i$

$y_i=x_i-10$的要大于等于0

所以插板法

$\sum_{i=0}^k\binom{k}{i}(-1)^i\binom{n-10i+k-1}{k-1}$

所以这个题也能变成这个问题

$x_2+x_4...x_2k-x_1-x_3...-x_{2k-1}=9k+x_{2k+1}/2$

钦定y_i=9-x_i

$x_2+x_4...x_2k+y_1+y_3...+y_{2k-1}=9k+x_{2k+1}/2$

会发现0<=x,y<=9

枚举x_{2k+1}容斥

如果n是4k+3形我们可以枚举开头结尾三个数再容斥

但是n是3要特判一下(全枚举了)

$A=(i,j)|a_i<a_j$

$B=(i,j)|b_i<b_j$

$C=(i,j)|c_i<c_j$

求A交B交C

容斥一下就好

A交B+B交C+C交A+A+B+C+U=|A交B交C|+|U除去(A并B并C)|

前面A交B可以二维数点$O(nlogn)$

后面两个式子发现值是相等的,所以答案就是前面的值除2就好了...

$O(nlogn)$

容斥原理,普及了

minmax容斥

$max{S}=\sum_{T\in S}(-1)^{T+1}min{T}$

T2ARC096E

容斥,不妨设为1~i

子集族分为两类,第一类含有1~i中至少一个,第二类是不含有

第二类:$2^{2^{n-i}}$,每个子集选或不选而已

枚举第一类的个数相当于有i个数字要分入k个集合

但是这些集合可能有大于i的部分

大于i的可有可无$*(2^{n-i})^k$

i个数字可能不放完?用一个垃圾堆,没有出现的向里面丢

可能没有一个出现的数字,也不知道哪个是垃圾堆

额外多一个0丢进去

满足垃圾堆非空,有0的就是垃圾堆,

答案是$S_{n+1,k+1}$

于是我们就做完了

$Ans=\sum_{i=0}^n(-1)^i\binom{n}{i}F(i)$

$F(i)=\sum_{k=0}S_{i+1,k+1}2^{k(n-i)}$

$*4^{n-i}$

T3ARC093F

先画出图,我们发现对于一个排列P,我们遇到的是

$p_2,min(p_3,p_4),min(p_5...p_8)$

然后设$G_1=p_2,G2=min(p_3,p_4)...$

$G_k=2^{k-1}..2^{k}$

所以这些G的最小值要没有A,都 不 在

考虑容斥

枚举一个子集$S \in {G1,G2,G3,G4....}$

$S_min都在A中$

F(S)为方案

$Ans=\sum_{i=0}(-1)^{|S|}F(S)$

对A,DP

从大到小考虑每个元素

问题是怎么分配一堆数字给$g_k$然后$min=a_i$

剩下的数字$>a_i$选出这么多

怎么知道已经选走了那些数字?

你会发现S中最小值都比$a_i$大!,所以每个元素都大,整个集合都在这一段里面

剩下$2^{n}-a_i-\sum_{j \in S} 2^j=R$

方案数$\binom{R}{2^k-1}$

->$f_{i-1,S+k}$

或$f_{i-1,S}$

剩下有若干数字,随意分配

F(S)=f_{0,S}*R!

做完了

小z的礼物

$E[Max_{x \in S}{t_x}]$

$=\sum_{T \in S}(-1)^{|T|+1}E[min{T}]$

每k个点对包含T中至少一个

$E[min(T)]=k/(n(m-1)+m(n-1))$

四相邻的要减1啊....

只有横着两个竖着两个要-1

所以可以DP

$dp_{i,j,S}$表示我们考虑了i行j列S是每一行考虑的最后一个点在不在其中

1.不在T直接转移

唉?T在哪啊?

把整个k塞入状态

2.如果属于T

考虑四个方向有没有选好的T

如果有说明要算重,减去即可

k要变成k'

直接DP,k一维是O(nm)的

$O((nm)^22^n)$

dp完,我们是对于一个T做的

统计每一个k对应多少个T

然后就可以算下贡献?

$ans=\sum_{T \in S}(-1)^{|T|+1}E[min{T}]$

k个点对包含了T当中至少一个点

再计入一个0/1表示T大小奇偶性?

斯特林反演

$n^m$组合意义是m个球放进n个盒子里

我们可以枚举i表示有多少个非空盒子,然后有标号$\sum_{i=1}^n \binom{n}{i}S_{k,i}i!$

有了下降幂就有上升幂

x^{{n升}=\sum_k[n,k]x}k

利用归纳法以及斯特林递推公式即可证明

f_n=\sum_{k=0}^nS_{n,k}g(k)$

->

$g(n)=\sum_{k=0}^n(-1)^{n-k}[n,k]f(k)$

引理,反转公式

反转公式引理

${x^n.}=(-1)^n(-x)^{n`}$

${x^n`}=(-1)^n(-x)^{n.}$

展开即可

反转公式

$\sum_{k=n}^m (-1)^{n-k}[n,k]{k,m}=[m=n]$

$\sum_{k=n}^m (-1)^{n-k}{n,k}[k,m]=[m=n]$

证明:利用之前某个引理,然后斯特林展开,然后提出多项式对应化简即可

利用第一个反转公式直接带入$f_n=\sum_j^n[j==n]f_j$即可从右向左证明斯特林反演!

T1

先整出任意两行不同方案

容斥!

第一行为$c^m$,第二行为$c^m-1$....

c^m^{m.}即m次下降幂

两列可能一样

$f_m$为任意两行两列不同的答案

怎么用f表示g

枚举有多少个本质不同的列

$g_m=\sum_{i=1}^m f_i S{m,i}$

然后斯特林反演

$f_m=\sum_{k=0}^m (-1)^{m-k} [m,k]g(m)$

$O(n^2)$

有标号的放入无标号集合就变得有标号了qwq

如果两个都是有标号的我们就会导致算重的问题QAQ

T2

设$c_u$表示点u到root的时间

求$E[c_u^k]$

$=E[\sum_{i}^k i! S_{k,i} \binom{c_u}{i}]$

$=\sum i! S_{k,i} E[\binom{c_u}{i}]$

后面怎么求?

第一种情况留在原地,第二种走出去

$=p_u*E(\binom{c_u+1}{i})+(1-p_u)/d_u*\sum_{v \in d(u)}sE(\binom{c_v+1}{i})$

利用组合数递推

$=p_u*E(\binom{c_u}{i}+\binom{c_u}{i-1})+(1-p_u)/d_u*\sum_{v \in d(u)}sE(\binom{c_v}{i}+\binom{c_v}{i})$

其中i-1那一项由期望线性型已经可以分离并已知了

$f_u=p_u(a_u+f_u)+1-p_u/d_u\sum(f_v+a_v)$

$d_u/(1-p_u)f_u=d_up_u/(1-p_u)(a_u+f_u)+\sum(f_v+a_v)$

$d_uf_u=d_up_u/(1-p_u)(a_u)+\sum(f_v+a_v)$

硬猜$f_u$可以表示成$f_fa_u+t$

假设u的所有孩子都有这个结论成立,那么u也有这个结论成立

$d_uf_u=d_up_u/(1-p_u)(a_u)+\sum(f_u+t_u+a_v)+f_fa+a_fa$

$f_u=d_up_u/(1-p_u)(a_u)+\sum(+t_u+a_v)+f_fa+a_fa$

所以我们先从下往上推一遍得出所有的t

又因为$f_1=0$

所以我们就能O(n)求出一个i的答案

然后我们做k遍,$O(nk)$

斯特林数需要用NTT优化

完蛋了效率好低啊

T是指对于所有的无向图,枚举了的连通块个数

$\sum T^k=\sum_{i=0}^k S_{k,i} i! \sum_{T} {\binom{T}{i}}$

$\binom{T}{i}$

$dp_k{n}$表示n个点恰好成为k个连通块的方案数

$\sum_T\binom{T}{i}=\sum_{j=1}dp_i{j}2^{\binom{n-j}{2}}$

然后把组合数拆开我们就能的到一个卷积形式

就可以卷卷卷啦!

但是$dp_i{j}$怎么求?j个点凑齐i个连通块

$dp_k{n}=\sum_{i}^n\binom{n-1}{i-1}dp_1{i}dp_k-1{n-i}$

这个东西拆开组合数还是能卷积啊?

但是要分治fft?

只要能有$dp_1$!!!

n个点连通图个数

容斥,总的减去不合法的

$2^{\binom{n}{i}}-\sum_{j}^{n-1} f_j 2^{\binom{n-j}{2}}$

左右中分别设生成函数为F,G,H

F=G*H

G=F/H多项式求逆qwq

总复杂度$O(nklogn+Tk)$

Burnside引理

放弃!

杂题选讲

$S_{i,j}j!=\sum_{k=0}^i(-1)^k\binom{j}{k}(j-k)^i$

$=\sum_{k=0}^n 2^j j! \frac{(-1)^(j-k)}{(j-k)!}\sum_{i=0}^n\frac{k^i}{k!}$

$Ai=\frac{(-1)^i}{i!}$

$Bi=\frac{\sum_{i=0}^n i^k}{i!}$

Ai和Bi卷一下

T2

假如第i个括号选了$x_i$

$\sum_{x} \prod_{i=1}^n E[b_{x_i}==i]$

$\sum_{x}E[\prod_{i=1}^n[b_{x_I}==i]]$

有重复元素就是0

否则就是固定了l个位置,他们一定要是给定的值,那个中括号连乘起来才能有值,剩下的就是随便填

概率就是

$1/k^L$

有$n^{L.}$种方案期望就是

$ans=n^{L.}/k^L$

F!=1

相当于我们重复了F次

$\sum_{x}\prod_{i=1}^L\prod_{j=1}^F[b_{x_{i,j}}==i]$

0,1变量相当于概率了

假如说有T个不同的元素

$1/k^T$

$n^{T.}$

然后变成有一个集合我们有R个元素要放入F个东西,相当于F个东西每一组都是非空的

方案数为$S_{F,R}$

然后单独算出来每一个盒子里面放R个元素的方案数

然后T个元素分入L个盒子的方案数就是这个东西背包卷积起来QAQ

实际上我们T只有2333的范围因为$n^{T.}$T>2333膜出来是0