本文参考：bztMinamoto和露迭月巨佬的博客 前置知识：对生成函数有一定了解，有概率期望的一定基础。 定义：一个生成函数F(x)，第i位表示某某为i的概率。 例题：[CTSC2006]歌唱王国 题意： 给定一个长度为的序列。然后每次掷一个平骰子（有m种值）并将其上的数字加入到初始为空的序列的末尾，如果序列中已经出现了给定序列，即是的子串，则停止。 题解： 设为时间停止的概率，为时间不停止的概率，,分别为它们的生成函数。 这其实是 考虑对这个式子做出变形，两边同时求导 对取, 考虑求出 介绍一个东西:对于一个长度为的序列，若，则称是的一个 定义=是 将带入 用或求出即可。 代码: #...

决策单调性（Flush Hu ） 这有什么用？ 这能优化dp。 决策单调性和斜率优化差不多。 需要细心发现决策之间的递变规律。 比如： 决策单调性有两种做法： 1.二分栈(队列)： 决策二分栈（一种单调栈）来维护所有有用的决策，其中栈顶是当前最优决策。 2.分治： 然而二分栈有一个局限性，那就是必须能快速计算。如果不能算的话，在求临界值k的时候复杂度会严重退化。 既然转移过程是单调并且离线的，我们考虑分治。假设当前我们求解一段区间,而所有的最优决策点在之间。对于的中点，我们可以暴力扫一遍，找到它的最优决策点。因为决策单调，所以的决策落在上，而的决策落在上，变成了两个规模减半的小问题。 3...

2-sat 题目：[模板]2-SAT 问题 题目描述: 有n个布尔变量，另有m个需要满足的条件，每个条件的形式都是“为true/false或为true/false”。比如“为真或为假”、“为假或为假”。2-SAT 问题的目标是给每个变量赋值使得所有条件得到满足。 题解： 0表示不选，1表示选 1.a=0 , a->a' 2.a=1 , a'->a 3.a=1那么b=1 , a->b b'->a'(隐藏b=0那么a=0) 4.a=0那么b=0 , a'->b' b->a(隐藏b=1那么a=1) 5.a=1那么b=0 , a->b' b-&g...

三元环是什么？ 三元环是 求无向图的三元环有两种方法： 做法1： ①统计每个点的度数 ②入度$sqrt(m)$的分为第二类 ③对于第一类，暴力每个点，然后暴力这个点的任意两条边，再判断这两条边的另一个端点是否连接因为m条边最多每条边遍历一次，然后暴力的点的入度，所以复杂度约为 ④对于第二类，直接暴力任意三个点，判断这三个点是否构成环，因为这一类点的个数不会超过$sqrt(m)个，所以复杂度约为$$O(sqrt(m)^3)=O(msqrt(m))$ ⑤判断两个点是否连接可以用set，map和Hash都行,根据具体情况而行这种做法建的是双向边，常数很大 #include using ...

同余最短路是什么？ 就是没个点i的意义是在模mn的意义下能被构造出来的最小值 这有什么用呢？ 这可以用最短路的方法求的余数是的最小能构造出来的数 这就可一求1-k中有多少数能被构造出来，即若干个a1到an的和 dis[(u+a[i])%mn]=min(dis[(u+a[i])%mn],dis[u]+a[i]) 题目：跳楼机 Srwudi的家是一幢h层的摩天大楼。由于前来学习的蒟蒻越来越多，srwudi改造了一个跳楼机，使得访客可以更方便的上楼。 经过改造，srwudi的跳楼机可以采用以下四种方式移动： 向上移动x层； 向上移动y层； 向上移动z层； 回到第一层。 一个月黑风高的大中午，DJ...

算法介绍： 李超线段树是一种用于维护平面直角坐标系内线段（直线）关系的数据结构。 它常被用来处理这样一种形式的问题： 给定一个平面直角坐标系，支持动态插入一条线段（直线），询问从某一个位置横坐标x从上向下能看到的最高的 一条线段（也就是给一条竖线，问这条竖线与所有线段的最高的交点。） 主要思想： 对整个横坐标建线段树，每个节点的值存的是一条直线的编号。 要求这条直线在横坐标为mid的时候纵坐标最大。 插入： 如果是叶子节点，我们直接保留最大的。 先比较斜率，再比较横坐标为mid时的纵坐标。 如果新线段的斜率大，并且横坐标为mid时的纵坐标大，那么把原线段下放左区间，节点值改为x 如果新线段的斜...

模拟退火 模拟退火能解决三分这类的问题，当然能解决三分不能的（暂时还不太会） 它能求出单峰函数的极值。 具体实现： 时间t初值为区间大小，每次乘上delta，delta一般设为0.992333 每次改变位置（先大范围跳，在小范围跳），计算答案，如果更优就更新，不优就用一个概率去选择更新 void tui() { t=1000;//温度初值 while(t>1e-12) { X=x+(rand()*2-RAND_MAX)*t*0.0001;//改变位置 if(X1000)X=1000;//判断边界 now=suan(X...

题目： 给你一棵树，节点从到编号，每个节点有一个权值，有若干次操作，操作有以下两种： <!--more--> ：将编号为的点的权值改为 :询问将号节点为根的子树中的所有叶子结点与子树外的其他所有叶子节点分离的最小代价，分离可以通过删除节点实现，删除一个节点的对应代价为该点的权值 数据范围：，任意均为非负数，答案在范围内 题解： 这题是经典的动态DP。 这种题往往是没修改时是普通的DP，然后加上修改操作，就要用树剖或LCT进行维护。 维护也有两种形式，一种纯粹是维护一个DP方程，一种是把DP方程转换为一个新定义矩阵然后像矩乘一样转移。 我还是用树剖维护一个DP方程，我觉得这...

题目： 其中 表示 的约数个数。 题解： 首先有 具体证明我不会，见他人博客 设 发现了什么，这个式子是不是就是 #2476. 「2018 集训队互测 Day 3」蒜头的奖杯 中的 然后，我们来推一下这个式子，感觉这个式子还是蛮重要的。 首先: 常规莫比乌斯反演, 令 这一步我不是很看得懂，手动模拟后发现就是和的卷积后的位之和 然后我们设，原式就变成： 看那几个不爽（因为莫比乌斯反演喜欢的形式）,设 枚举然后，所以 因为一定是的倍数，一定是的倍数，我们再把换成，即枚举，A,B现在的坐标为 我们在把换成， 这是当是已知的话（即枚举）， 设 如果 与 已知（同样枚举） 那么就得到了，...

题目：[TJOI2019]甲苯先生和大中锋的字符串 大中锋有一个长度为 n 的字符串，他只知道其中的一个子串是祖上传下来的宝藏的密码。但是由于字符串很长，大中锋很难将这些子串一一尝试。 这天大中锋找到甲苯先生算命，但是甲苯先生说：“天机不可泄漏”。 在大中锋的苦苦哀求下，甲苯先生告诉大中锋：“密码是在字符串中恰好出现了 kk 次的子串”。 但是大中锋不知道该怎么做，在大中锋再三的恳求下，甲苯先生看其真诚，又告诉他：“在恰好出现了 k 次的子串中，你去按照字串的长度分类，密码就在数量最多的那一类里”。 大中锋为了尝试这个密码，想让你帮忙找出子串长度出现次数最多的长度数（如果有多个输出最长长度）。...

前言: 如果你不会线性基，希望能对你有点帮助。 作者较菜，请大佬轻表。 请大家多多支持，谢谢 定义： 基：在线性代数中，基（也称为基底）是描述、刻画向量空间的基本工具。向量空间的基是它的一个特殊的子集，基的元素称为基向量。向量空间中任意一个元素，都可以唯一地表示成基向量的线性组合。如果基中元素个数有限，就称向量空间为有限维向量空间，将元素的个数称作向量空间的维数。 同样的，线性基是一种特殊的基，它通常会在异或运算中出现，它的意义是：通过原集合S的某一个最小子集S1使得S1内元素相互异或得到的值域与原集合S相互异或得到的值域相同。(摘自百度百科) 性质： 1. 线性基能相互异或得到原集合的所有相...