在此处输入标题

杂题选讲

在此输入正文
baka数：只含有2和9的数字
问1-10^10中有多少数能被baka数整除

容斥

相似子串
定义： 长度相同，最多只有一位不同
给定一个字符串，每次询问两个子串是否相似？

只考虑条件2：进行字符串hash
去质数31
则
a= aca
b=aba
则查看a与b的hash值差为是否为31的几次方

next：
等价关系：

s1： h1=hash[a]+hash[b]....
s2： h2=hash[a] +hash[b]....
若h1==h2则s1与s2相等

222.2：标记字符‘a’ ‘b’.....‘c’标记位置
查看在两个串中是否相同

只考虑条件1： strlen

treecnt

n个节点数，抽离出k个点，连边
计算对于所有选择k个点的情况最小选择的边数
性质：1.一条边被删掉的话树会被分为两部分

组合数取mod
对分母求一个逆元，然后就乘一下

逆序对数列

求逆序对为k的数列有多少个？

f[i][j]表示1~i这几个数字 构成有多少排列满足逆序对数为j的排列的个数

转移：插入第i+1个数，共有i+1位置可以插入，（如放在最前面会增加i个逆序对），f[i][j]可以推出-->f[i+1][j],f[i+1][i+j];
f[i-1][j]~~f[i-1][j-i+1],由此可以做一个前缀和优化，

玩具取名

状态f[I][J]第i个字母到第j个字母形成的字符串能否被原子串转移过来
w->in
f[i][j][w]
f[i][j][i]&&f[k+1][j][n]->f[i][j][w]

硬币购物

一共四种硬币面值为 a b c d，
某人去商店买东西，去了tot次每次带ci硬币di个
买si的价值的东西，请问每次有多少种付款方式：
<=100000

解法1rongchi容斥
求出没有硬币限制下si的方案数；
减去某种硬币用了不只di枚的方案数：（求法：<强制用超>先用掉第di+1枚，求出在该情况下有多少方案数，）把这些情况减去，然后加上两枚同时用超情况......容斥一下；
f[si]-f[si-(d1+1)*c1]-f[si-(d2+1)*c3]-f[si-(d3+1)*c3]
.....
+f[si-(d1+1)*C1-(d2+1)*c2]......

-f[si-(d1+1)*c1-(d2+1）*c2-(d3+1)*c3].......

<--------------------- 图论------------------>

欧拉图

首先判断是否是一个连通图

欧拉路径：
1：判断联通
2：最多两个点的度数为偶数（起点，终点）；

输出路径：
dfs瞎jb搞，一笔画序列；