数学虐哭空巢老人记

数学虐哭空巢老人记

总结梳理：

学习过的东西

  • 基础数论（gcd、exgcd、lucas、exlucas、bsgs、exbsgs）
  • 一些数字（卡塔兰数、组合数、第一类斯特林数、第二类斯特林数、贝尔数、斐波那契数列）
  • 多项式运算及生成函数（FFT、NTT、MTT、FWT）
  • 一些筛法（埃氏筛法、杜教筛、Min_25筛）
  • 一些反演（莫比乌斯反演、二项式反演、单位根反演、斯特林反演、(k)Min_max容斥）
  • 其他（矩阵树定理、prufer序列）

还没有学到的东西

  • 类欧几里得算法
  • Burnside/Polya定理
  • 快速莫比乌斯变换（FMT）
  • 线性规划
  • 常系数齐次递推（BM）
  • 多项式多点求值
  • 多项式插值

我不管我先搬之前写的东西：

多项式Review（yyb）

注意点&Trick

1.长度问题

两个最高次项分别为n和m的多项式相乘，长度应该为>n+m的最小的2的幂(l)，乘出来只会在([0,l))内有值

2.构造问题

如何构造多项式？

记住一点：把对应关系画出来，找到规律再卷积！

  • 字符串匹配

    一类(i=j)型相乘，直接reverse其中一个即可

  • 组合数类型

    (sum_{i=1}^{n}RC(i,k)=frac{1}{n!}sum_{i=1}^{k}frac{R_1i!}{R_2(i-k)!})

    构造(A[i]=R_1i!,B[i]=frac{1}{R_2(n-i)!})

    那么卷积起来后(C[n+k]=sum_{i=1}^{n}A[i]*B[n+k-i]=sum_{i=1}^{n}frac{R_1i!}{R_2(i-k)!}​)

题目

  • [x] 洛谷 1919 A*B Problem 升级版 (skip)

  • [x] SDOI2015 序列统计

    数集S中选择一个可重排列使得排列内的数字乘积和%M=x的排列个数

由于M是质数，存在原根，所以将乘法变成原根的加法，具体来说，用$a_1g^1+a_2g^2+...+a_ng^n$表示选择各个数字的方案数，合并的话卷积就好了，用二进制快速幂实现

  • [ ] HZOI2015 帕秋莉的超级多项式

  • [x] CF954I Yet Another String Matching Problem

    pre：两个长度为n的字符串，每次可以花费1的代价，指定两个字母，把其中一个全部变为另一个，求使两个字符串相同的最小花费

sol：相同位置如果字母不同则用并查集并起来，合并次数即为答案

pro：字符集为6，问S的每个子串和T做上述问题的答案

sol：把T给reverse，做6*6次FFT，若A[|T|+i]上有值则说明这两个字母在i位置上需要并查集合起来，然后依次判断每个位置上的并查集个数即可

  • [x] BZOJ3160 万径人踪灭

    字符集为2的字符串求其一个子序列使得在原串上不全连续且关于某处对称

对于两个字符分别考虑，对S做卷积之后i位置上的值为k则表示有k/2对字符关于i/2位置对称，加上$2^k-1$的贡献，之后减去完全连续的，用Manacher计算即可

  • [x] BZOJ4503 两个串

  • [x] BZOJ4259 残缺的字符串

    双倍经验，两串有通配符，求从某位置开始是否能进行模糊匹配

把26个字母转为数字，通配符为0，检查$F(x)=sum_{i=1}^{|T|}(S[x+i-1]-T[i])^2S[x+i-1]T[i]$是否为0即可

  • [x] CF528D Fuzzy Search

    模糊匹配，字符集${A,C,T,G}$，两串相同字符距离不超过k即可算作匹配上，求模式串在文本串中出现的次数

做4次，若S串的i位置为1，把$i-k$到$i+k$都设为1，FFT后某位置累计匹配字符个数为$|T|$即符合条件

  • [x] HNOI2017 礼物

    两个换，其中一个可以旋转，求$sum_{i=1}^{n}(x_i-y_i)^2$的最小值

拆了之后就是卷积最小值，那么只需要A串倍长，B串翻转，卷积后求结果序列的最小值即可

  • [x] ZJOI2014 力

    式子拆开后两遍FFT即可

  • [x] Tjoi2016&Heoi2016 求和

  • [x] HAOI2018 染色

  • [x] AGC005F Many Easy Problems

    对于k=1->n，求包含树上任意k个点的点集的联通块大小之和

考虑每一个点的贡献（期望的线性性），就是以其为根、自己选或至少两个子树选的方案数

容斥一下成为$C(n,k)-C(siz[son],k)$，只出现在一个子树内的情况不合法

求和之后套入组合数NTT即可

  • [x] CQOI2014 通配符匹配

    有两种通配符，一种匹配一个，一种匹配任意多个，求两串是否能够匹配，通配符个数不超过10

动态规划解决，状态为匹配上i个通配符，匹配到第j个位置是否可行，转移用哈希判断

多项式并不能解决此题

  • [x] luogu4726 多项式exp

  • [x] luogu4721【模板】分治 FFT

    给定$g(x)$求解$f(x)=sum_{i=1}^xf(x-i)g(i)$

很像卷积，但是前面的对后面有影响，考虑CDQ。

分治到$(L,R)$，则$f(L,mid)*g(0,R-L)$的第$k$项对$f(k-mid)$有贡献（画两排点去推一下）

```cpp
void CDQ_FFT(int *a,int *b,int L,int R)
{
	if(L==R) return;
	int mid=(L+R)>>1,len=R-L+1,tt=0;
	CDQ_FFT(a,b,L,mid);
	for(l=1;l<=len*2;l<<=1) tt++;tt--;
	for(int i=0;i<l;i++) r[i]=(r[i>>1]>>1)|((i&1)<<tt);
	for(int i=0;i<l;i++) A[i]=B[i]=0;
	for(int i=L;i<=mid;i++) A[i-L]=a[i];
	for(int i=0;i<=R-L;i++) B[i]=b[i];
	NTT(A,1);NTT(B,1);
	for(int i=0;i<l;i++) A[i]=1ll*A[i]*B[i]%mod;
	NTT(A,-1);
	for(int i=mid+1;i<=R;i++) (a[i]+=A[i-L])%=mod;
	CDQ_FFT(a,b,mid+1,R);
}
```

​

  • [x] luogu4512【模板】多项式除法

  • [x] BZOJ3771 Triple

    求n个物品中选走1或2或3个的价值和以及方案数

构造生成函数$A(x)=sum cnt_ix^i$，表示价值为i的物品有$cnt_i$个

令$B(x)=sum cnt_i^2x^{2i}$，$C(x)=sum cnt_i^3x^{3i}$，分别表示同一种物品选了多次需要减去的生成函数

则选一个：$A(x)$。选两个：$frac{A^2(x)-B(x)}{2}$。选三个：$frac{A^3(x)-3*A(x)B(x)+2*C(x)}{6}$。相加即可

  • [x] CF438E The Child and Binary Tree

    在给定数集中选择若干个点作为二叉树的权值，要求权值和为n，求不同二叉树个数

设$G(x)=sum a_ix^i$，表示权值和为i的二叉树有$a_i$种情况

设$F(x)=sum b_ix^i$，表示点权i是否在数集中出现过

考虑二叉树的生成方式可得：$F(x)G^2(x)+1=G(x)$，表示新增一个点，左右儿子方案数为$G^2(x)$，还有空树的方案数。接下来套用多项式开放&求逆，把不能开方的解舍掉即可

  • [x] BZOJ3028 食物

    一个人带n种物品的方案数，要求n种物品只能带$w_i$的倍数个或者一些奇怪的限制条件

裸生成函数，用初一的因式分解化简后得到$frac{x}{(1-x)^4}$

考虑其组合意义，$frac{x}{(1-x)^4}=x(1+x^2+x^3+...+x^inf)^4$，表示把$n-1$划分成$4$个自然数的方案数

即$n$个空位插$3$个隔板的可重组合$C({n+3-1},3)=C(n+2,3)$

  • [x] BZOJ3456 城市规划

  • [x] luogu4233 射命丸文的笔记

  • [x] 有标号的 DAG 计数 I

  • [x] 有标号的 DAG 计数 II

  • [x] 有标号的 DAG 计数 III

  • [x] 有标号的 DAG 计数 IIII

  • [x] HDU5730 Shell Necklace

  • [x] luogu4389 付公主的背包

  • [x] luogu4705 玩游戏

  • [x] loj6261 一个人的高三楼

  • [x] loj6089 小 Y 的背包计数问题

多项式运算（for instant access）

运用牛顿迭代（泰勒展开式）可得

[B_{t+1}(x)=B_t(x)-frac{F(B_t(x))}{F'(B_t(x))} ]

其中(F(B(x)))表示一个需要值为0的函数，如求逆时构造(F(x)=A(x)B(x)-1)，注意求导不是复合函数求导，而是把(B(x))当自变量，对(F(x))求导

求导

[B[i]=A[i+1]*(i+1) ]

求积分

[B[i]=frac{A[i-1]}{i} ]

求逆

[B_{t+1}=2B_t-AB_t^2 ]

开方

[B_{t+1}=frac{1}{2}(B_t+frac{A}{B_t}) ]

求ln

[B=lnA,B'=frac{A'}{A}$$再积回来 ### 求exp $$B_{t+1}=B_t(A-lnB_t+1)]

除法

(F(x)=A(x)G(x)+B(x))，(F(x))最高项为n，(G(x))最高项为m，则(A(x))最高项为n-m，(B(x))为m-1

(F^R(x)=A^R(x)G^R(x)+x^{n-m+1}B(x),A^R(x)=frac{F^R(x)}{G^R(x)}(mod x^{n-m}))，回代求解B(x)

求exp的模板代码（包含除开方/除法的所有操作）

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int mod=998244353,N=4e5+10;
int n,r[N],l,tt,inv[N],A[N],B[N],C[N],D[N];
int E[N],F[N],G[N],H[N],I[N],w[N];
int ksm(int x,int k)
{
	int s=1;for(;k;k>>=1,x=1ll*x*x%mod)
				if(k&1) s=1ll*s*x%mod;return s;
}
void NTT(int *P,int op,int l)
{
	int tt=0;for(int w=1;w<l;w<<=1) tt++;tt--;
	for(int i=1;i<l;i++) r[i]=(r[i>>1]>>1)|((i&1)<<tt);
    for(int i=1;i<l;i++) if(r[i]>i) swap(P[i],P[r[i]]);
    for(int i=1;i<l;i<<=1)
    {
        int W=ksm(3,(mod-1)/(i<<1));
        if(op<0) W=ksm(W,mod-2);w[0]=1;
        for(int j=1;j<i;j++) w[j]=1ll*w[j-1]*W%mod;
        for(int j=0,p=i<<1;j<l;j+=p)
            for(int k=0;k<i;k++)
            {
                int X=P[j+k],Y=1ll*P[j+k+i]*w[k]%mod;
                P[j+k]=(X+Y)%mod;P[j+k+i]=(mod+(X-Y)%mod)%mod;
            }
    }
	if(op<0) for(int i=0,in=ksm(l,mod-2);i<l;i++) P[i]=1ll*in*P[i]%mod;
}
void GetInv(int *a,int *b,int len)
{
	if(len==1) {b[0]=ksm(a[0],mod-2);return;}
	GetInv(a,b,len>>1);
	for(int i=0;i<len;i++) A[i]=a[i],B[i]=b[i];
	NTT(A,1,len<<1),NTT(B,1,len<<1);
	for(int i=0;i<len<<1;i++) A[i]=1ll*A[i]*B[i]%mod*B[i]%mod;
	NTT(A,-1,len<<1);
	for(int i=0;i<len;i++) b[i]=(2ll*b[i]%mod-A[i]%mod+mod)%mod;
	for(int i=0;i<len<<1;i++) A[i]=B[i]=0;
}
void GetDao(int *a,int *b,int len)
{
	b[len-1]=0;
	for(int i=0;i<len-1;i++)
		b[i]=1ll*a[i+1]*(i+1)%mod;
}
void GetJifen(int *a,int *b,int len)
{
	b[0]=0;
	for(int i=1;i<len;i++)
		b[i]=1ll*a[i-1]*inv[i]%mod;
}
void Getln(int *a,int *b,int len)
{
	GetDao(a,C,len);
	GetInv(a,D,len);
	NTT(C,1,len<<1);NTT(D,1,len<<1);
	for(int i=0;i<len<<1;i++) C[i]=1ll*C[i]*D[i]%mod;
	NTT(C,-1,len<<1);
	GetJifen(C,b,len);
	for(int i=0;i<len<<1;i++) C[i]=D[i]=0;
}
void Getexp(int *a,int *b,int len)
{
	if(len==1) {b[0]=1;return;}
	Getexp(a,b,len>>1);
	Getln(b,G,len);
	for(int i=0;i<len;i++) E[i]=b[i],F[i]=(mod-G[i]+a[i])%mod;(F[0]+=1)%=mod;
	NTT(E,1,len<<1),NTT(F,1,len<<1);
	for(int i=0;i<len<<1;i++) E[i]=1ll*E[i]*F[i]%mod;
	NTT(E,-1,len<<1);
	for(int i=0;i<len;i++) b[i]=E[i];
	for(int i=0;i<len<<1;i++) E[i]=F[i]=G[i]=0;
}
int main()
{
	cin>>n;n--;
	for(int i=0;i<=n;i++) cin>>H[i],H[i]%=mod;
	for(l=1;l<=n;l<<=1);
	inv[0]=inv[1]=1;
	for(int i=2;i<=l;i++) inv[i]=(mod-1ll*mod/i*inv[mod%i]%mod)%mod;
	Getexp(H,I,l);
	for(int i=0;i<=n;i++) printf("%d ",I[i]);
	return puts(""),0;
}

数论专题（gxy）

算法

杜教筛

zzq总结：https://www.cnblogs.com/zzqsblog/p/5461392.html

推荐博客：https://blog.csdn.net/skywalkert/article/details/50500009

yyb题单：http://www.cnblogs.com/cjyyb/category/1148840.html

扩展卢卡斯

Min_25筛

yyb总结：https://www.cnblogs.com/cjyyb/p/10169190.html

ycb总结：https://www.cnblogs.com/GuessYCB/p/10061411.html

各种筛

  • [ ] [BZOJ3309] DZY Loves Math
  • [ ] [CQOI2017] 小Q的表格
  • [ ] [Luogu4240] 毒瘤之神的考验

(ex)BSGS

就是两个板子，见博客：orzzzzsy

自己的代码习惯：BSGS、EexBSGS

题目

组合数公式

1、(C_{m+r+1}^r=sum_{i=0}^{r}C_{m+i}^{i})

2、(sum_{i=0}^mC_m^i*x^i=(x+1)^m)，推广到(x=-1)

3、(sum_{i=1}^nC_n^i*i=n*2^{n-1})

4、(sum_{i=1}^n{ichoose a}{n-ichoose b}={n+1choose a+b+1})，范德蒙恒等式

卡塔兰数公式

定义第0项开始为：1,1,2,5,14,42,132,429......

1、定义式：(C[n+1]=C[0]C[n]+C[1]C[n-1]+C[2]C[n-2]+...+C[n]C[0])

2、递推式：(C[n+1]=frac{C[n]*(4n-2)}{n+1})

3、组合式：(C[n]=frac{C(2n,n)}{n+1}=C(2n,n)-C(2n,n-1))

斯特林数公式

第一类斯特林数

(s[i][j])表示把(i)个不同的球构成(j)个圆排列的方案数

1、递推式：(s[i][j]=s[i-1][j-1]+(i-1)*s[i-1][j])

2、性质式：(sum_{i=0}^ns[n][i]=n!)

第二类斯特林数

(S[i][j])表示把(i)个不同的球放进(k)个相同盒子里的方案数

1、递推式：(S[i][j]=S[i-1][j-1]+j*S[i-1][j])

2、NTT式：(S[n][k]=frac{1}{k!}sum_{i=0}^k(-1)^iC(k,i)(k-i)^n)

3、幂次式：(x^k=sum_{i=1}^xS(k,i)C(x,i)i!=sum_{i=1}^kS(k,i)C(x,i)i!)

​ 理解：(x^k)表示把(k)个有区别的球放入(x)个不同的盒子里，允许空盒的方案数

​ 可以表示成把(k)个球分到(i)个盒子，没有空盒的方案数，(i!)强行给盒子搞个差别

​ 循环上界都可以，因为一旦大于了其中一个式子就等于0了

贝尔数

(B[i])表示(n)的集合划分数

1、递推式：(B[n+1]=sum_{i=0}^nC(n,i)B[i])

2、取模式：(B[n+p]equiv B[n]+B[n+1] (mod p))

3、定义式：(B[n]=sum_{i=1}^nS[n][i])

斐波那契数列

定义自第1项起为1,1,2,3,5,8,13,21.....

1、通项公式：(F[n]=frac{sqrt 5}{5}[(frac{1+sqrt 5}{2})^n-(frac{1-sqrt 5}{2})^n])

2、前缀和公式：(sum_{i=1}^nF[i]=F[n+2]-1)

3、前缀平方和公式：(sum_{i=1}^nF[i]^2=F[n]*F[n+1])

4、前缀和公式变形：(sum_{i=1}^ni*F[i]=n*F[n+2]-F[n+3]+2)

5、前缀奇数项和公式：(sum_{i=1}^nF[2i-1]=F[2n]-F[2]+F[1])

6、前缀偶数项和公式：(sum_{i=1}^nF[2i]=F[2n+1]-F[1])

空巢专题（fdf）

矩阵树定理

Min_max容斥

二项式反演

单位根反演

斯特林反演

一些重要的反演式子

  • [sum_{i=0}^n {nchoose i}(-1)^i=[n==0] ]

    ​

唉我太菜了儿子们回来后这些东西都忘光了

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/xzyxzy/p/10365431.html