小衣同学的博客

第i行的主元并不一定在第i位，倒着遍历每一行，消去得到第i行的主元的解。钦定第i个点在第i位为1，解满足这n+1个限制条件的异或高斯消元方程。对于无穷解的情况，秩r<n，这里钦定所有自由元均为0，每个点非0，所以每个点占据二进制位中的一位，G. XOR Neighbors 为例。将相邻点的限制列为一个方程作限制，

对于一张无向图G，记D为其度数矩阵，满足：1. D[i][i]=i的度数记A为其邻接矩阵，满足：1. A[i][j]=i与j之间边的条数，如果有重边则算作多条边。记基尔霍夫矩阵（拉普拉斯矩阵）K=D−A，则去掉第k行第k列得到的矩阵行列式即为G生成树的个数。

引自tourist的哈希板子，引入和时间相关的随机值，所以不会被卡掉。入参：传入string。

题目为了知道自己的排名，小C使用了系统中的“好友伴学”功能。每次，系统会在除了小C之外的所有考生中随机抽取一名，然后返回Ta的排名比小C高还是低。这次考试有n(2<=n<=1e11)个人参加，可以认为小C的排名是一个在[1,n]内等概率随机的整数。小C总共使用的m(0<=m<=5e3)次“好友伴学”功能，却没有一次抽中排名比自己高的人。请问小C在这次考试中的期望排名是多少，若答案为，输出思路来源题解https://ac.nowcoder.com/d

所在的连通块多大，对应连通块和之前的二分图是在什么时候断裂的当大小为k时，从i-1个点中选k-1个点，再对应选出一些边有有了联通的二分图之后，再考虑如何合并计表示i个点j条边由若干个连通块组成、无重复的二分图转移仍然枚举最后一个点所在的连通块多大，从之前的f合法方案，通过背包转移到新的合法方案当大小为k时，从i-1个点中选k-1个点，再对应选出一些边有求出f[i][j]后，n个点是固定的，因为f[n-1][j]可以通过不用边的方式转移到f[n][j]

杨氏矩阵，又称杨表，杨表里去掉数字就是杨图对于n的一个整数拆分，满足，记作。

从右到左：只有处理好了第i+1列，才能处理第i列，(i,j)涂黑当且仅当(i+1,k)涂黑，k<=j+1。从左到右：只有处理好了第i-1列，才能处理第i列，(i,j)涂黑当且仅当(i+1,k)不涂黑，k<j-1。对于任意在矩阵中的(i,j)，即1<=i<=n且1<=j<=m，②若(i+1,j+1)也在矩阵中，则(i+1,j+1)也是黑块。某一列没有黑块的情形，此时，我把最后一个黑块定到了第n+1行，①若(i+1,j)也在矩阵中，则(i+1,j)也是黑块。因为(i,j)黑块取了的话，这一列下面的黑块都会取，

算法学习笔记(74): 二分图博弈 - 知乎。

题目思路来源定理：任何竞赛图都有哈密顿路径，强连通的竞赛图有哈密顿回路证明：https://blog.csdn.net/unsolvedmys/article/details/73608770题解竞赛图，相当于对C(n,2)条边的完全图定向，定为有向图由定理，对于任意竞赛图，最长链长度都为n所以，长度为1到n-1时输出0，为n时输出2的C(n,2)次方代码...

动态开点李超树（例题+板子总结）

计算几何（板子整理）

数论：预处理所有质因子&因子&因子个数&每个因子对应的质因子（知识点总结+板子整理）

记cf的一些tle写法1. unordered_map2. endl

kmp与扩展kmp（板子整理）1. kmp与最小最大表示法2. 扩展kmp的替代方案

CF/ATC/LC题目分数/近期比赛网址

前言cf群里，有人提了一个线段树区间连续1，不带修改的问题Claris口胡一个O(n)-O(1)的做法，于是来学习一下思路来源https://www.cnblogs.com/whx1003/p/13996517.html知识总结四毛子算法是一种暴力分块的思想，+-1RMQ是其应用之一①+-1RMQ问题（O(n)-O(1)）+-1RMQ问题是这么一个问题，仍然询问区间的RMQ，但是这个序列有着特殊的性质，即相邻项之差要么是-1，要么是+1，于是，有如下的暴力思想，先分块

假设编号依次是 0，1，2，...，n-1 的n个人围成一个环，从编号是0的人开始依次报数，从1报到m且报m的人从环里退出，后面的人重新从1开始报数，直到剩下一个人为止，问环里最后剩下的那个人的编号是多少？========================显而易见：n＞1时才涉及到报数退出，n=1时最后那个人的编号就是0；第一个退出的人的编号注定是 (m-1)%n；========================现在假设 n=10，m=30 1 2 3 4 5 6 7 8 9第一个人出

思路来源https://blog.nowcoder.net/n/5eaebd22f5f846838c637bc337cc1ee9知识点整理长链剖分，用于维护子树中只与深度有关的信息，多用于静态长链剖分，顾名思义，每个点维护子树中最长的那一条链，[l[x],l[x]+len[x]-1]是其长链区间，到l[x]的偏移量也确定了它的深度和dsu on tree类似，但若干条链分别占用不同位置的数组空间，只有相同链的内存共用，所以不用像dsu on tree那样清空内存，所以预处理.

思路来源https://www.cnblogs.com/stoorz/p/12388534.html板子https://www.cnblogs.com/zwfymqz/p/9175152.html构建过程、复杂度证明知识点整理以下部分来自https://www.cnblogs.com/zwfymqz/p/9175152.html维护一个栈，建虚树的时候分三种情况，一边dfs一边建即可一般考察虚树dp，复杂度是O(2*sumk)，因为加入一个点最多多一个lca板子整理把..

思路来源https://www.cnblogs.com/cjyyb/p/9185093.htmlhttps://www.cnblogs.com/zhoushuyu/p/9187319.htmlhttps://www.mina.moe/archives/12287心得这个从去年上个月就想学的知识，终于在开学前被学会了神仙min_25 QAQ 神仙zzt QAQ 神仙yyb QAQ学会min25筛比较难，但大概写一份能让初学者看懂的博客更难学会之后，发现这个东西很模板，抄个板子改

思路来源https://www.luogu.com.cn/blog/flashblog/solution-p3690https://www.cnblogs.com/19992147orz/p/8206693.htmlhttps://www.cnblogs.com/candy99/p/6271344.html前置知识splay：真正理解rotate、会区间翻转树链剖分：轻重链的概念心得杭电多校LCT的题，被120队过，不学新知识不行了，哎……强推第一篇洛谷题解，有图可供食用

后缀自动机(知识整理+板子总结)

思路来源https://www.cnblogs.com/zwfymqz/p/8869956.htmlhttps://www.luogu.com.cn/blog/xht37/solution-p6086https://www.luogu.com.cn/blog/hekaiyu/prufer-xu-lie知识总结常用于生成树计数，毕竟都搞出序列了。一个长度为n-2的Prufer序列，唯一对应一棵n个点固定形态的无根树。T->P(Tree->Prufer)找到编.

知识整理bitset卡常大法好，对于整个长度的操作单次复杂度以下是bitset的一些常用用法，转化为ull时，需保证不会溢出#include<bitset>using namespace std;const int N=15;bitset<N>x,y,z(255);int main(){ x[0]=1;x<<=1;y>>=1;...

板子模板框架，来源于Codeforces群winterzz1#include<bits/stdc++.h>using namespace std;typedef long long ll;#define pb push_backconst int N=2e5+10;vector<int>e[N];int sz[N],n,u,v;ll dp[N],an...

心得https://blog.csdn.net/Code92007/article/details/97396823学类欧的时候已经用过一些今天写个abc的D，调这个向上取整向下取整调了好半天，打完了还是总结一下吧正文在程序中，两个整数相除，无论a,b符号为何，a/b都会近零取整那远零取整怎么写呢，小学生不等式开课了以x=a/b，远零取整为例①a>0，b&g...

暑假学的，当时也没总结，今天又看到，怕再忘了吧……其实就还是dp的思想，搞来搞去这个样子……思路来源https://blog.csdn.net/qq_30358129/article/details/88044727最大01子矩阵题目可以用来交poj3494h[i][j]表示以(i,j)为最下位置的悬线的高度，l[i][j]表示(i,j)能拓到的最左位置，r[i][j]...

思路来源https://www.cnblogs.com/zwfymqz/p/8253530.html心得其实就是旋转坐标系，先旋转再伸缩一般曼哈顿距离直接做不好做的，可以转成切比雪夫距离试试看结论将一个点(x,y)的坐标变为后，原坐标系中的曼哈顿距离=新坐标系中的切比雪夫距离将一个点(x,y)的坐标变为后，原坐标系中的切比雪夫距离=新坐标系中的曼哈顿距离第二个显然...

思路来源https://www.cnblogs.com/Miracevin/p/9863080.html知识点整理原博主的图片，出树和入树 和 本代码里的tin和tout正好相反……两棵树，一棵tin树，一棵tout树，让tin[k]中的父亲向儿子连边，代表u向区间连边，让tout[k]中的儿子向父亲连边，代表区间向点u连边，让入树和出树的叶子结点指向相同的真实节点...

心得听说南京现场赛出了个KM然后卡kuangbin&&lrj板子...吓得我交一发hdu6346整理个板子，KM的bfs版本kuangbin的版本直接求是求最大权匹配，而该板子直接求是求最小权匹配第一个的是最好用的，不过还是多带几个板子，万一被卡了呢……代码1//KM模板//本题hdu6346 用于求二分图最大权匹配//如果边权不取反 则用于求...

#include <ctime>signed main(){ clock_t start,end; start=clock(); /* 代码块 */ end=clock(); printf("%.5lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000); return 0;}

思路来源https://baike.baidu.com/item/%E5%8D%A1%E7%89%B9%E5%85%B0%E6%95%B0/6125746?fr=aladdinhttps://blog.csdn.net/duanruibupt/article/details/6869431https://www.cnblogs.com/COLIN-LIGHTNING/p/8450053...

先考虑极端情况， 如果h(n)=0h(n)=0的情况下，只有g(n)g(n)起作用，那么A*算法就是Dijkstra算法。如果h(n)h(n)始终小于等于实际nn点到终点的距离，那么必然能够保证A*算法找的解就是最优解。而且h(n)h(n)越小，则A*扩展的节点也就越多，A*算法运行的也就越慢。如果h(n)h(n)始终都等于实际nn点到终点的距离，那么A*算法只会严格走从起点到终点的最短路径。虽然这种情况一般不可能发生，当然一些特殊情况下会发生【比如没有障碍物的情况】。如果h(n)h(n)有时候大于实

板子来源https://www.cnblogs.com/hefenghhhh/p/5051334.htmlhttps://www.cnblogs.com/Simon-X/p/5687318.html心得去年九月份学过的知识，就不再详细展开了，大概就是树上的KMP以前总用指针的，不好写，100多行，今天也搞一个数组的板子然后每个trie都是一个节点，节点与next...

概念和线段树一样的函数，p这个区间里维护的是这段区间里的数出现的次数每出现一个数x，叶子结点[x,x]这个区间就+1，删除就-1支持动态查询第k大的数、数x出现的最小rank、寻找x的前驱（即小于x的最大的数）和寻找x的后继（即大于x的最小的数）等操作思路来源https://www.bilibili.com/video/av16552942?from=search&...

概念主席树以前i个值建第i棵线段树，新来的值只会新开一条链，对于第一棵树而言，即普通的权值线段树，或者理解成一条链也无妨结构体的权值线段树写法利用前缀和的方法 统计[l,r]内各个数出现的数量前提保证a1-an均在1-n之间如果不在1-n之间就离散化一下搞成rank就到1-n之间了十一的时候学过这个东西但是当时只是看懂没有及时跟上例题和总结 然后...

思路来源https://www.tuicool.com/articles/ee2QZf6https://blog.csdn.net/creatorx/article/details/75805461概念直接扒过来了，懒得写了……显然轻子树比重子树小，就少于父亲的一半，然后性质2的证明就是基于此的……因为重链是间断的，所以两条重链夹着一条轻边，然后若重链x条，...

相当于总结一波，以后就从这里扒RMQ的板子个人觉得博客的这个粘代码背景没我的黑底白字好看QAQ代码总是越敲越熟的嘛……知识沉积的过程……到时候改一改，传参的时候把数组名一起传进去，就能当小黑盒用了法一（单调队列，O（n））：//区间连续k个的最小 传进去下标 deque<int>q; for(int i=1;i<k;++i) ...

视具体情况，改变maxn和mod，注意mod必为奇素数，才能用费马小定理，不然用扩展欧几里得代码typedef long long ll;const int mod=998244353; const int maxn=1e5;ll Finv[maxn+5],jc[maxn+5];ll modpow(ll x,ll n,ll mod){ ll res=1; for(;...

思路来源https://baike.baidu.com/item/%E5%8E%9F%E6%A0%B9/8103534?fr=aladdinhttps://blog.csdn.net/zoro_n/article/details/78200742https://www.cnblogs.com/Dance-Of-Faith/p/9905786.html《数学的思维方式与创新》 丘维声...