唉，不会线性代数了，做了三个小时。为了求行列式，显然要先把\(A\)消成上三角矩阵，记作\(A'\)。我们显然可以在操作\(A\)的时候求出将\(A\)消成\(A'\)的操作矩阵\(M\)，则我们可以构造\(A'=B'C'\)，再将\(B'\)乘上\(M^{-1}\)就可以得到原来的\(B\)。判掉\(A\)的行列式不

The2ndUniversalCup.Stage17:Jinan为了参加省赛打的模拟。打了八个题，稳稳金牌。E.IJustWant...OneMore...考虑如何计数，因此考虑方案的等价条件。一条边满足要求，当且仅当原图存在一种最大匹配，使得这条边的两个顶点都不在匹配中。而上述条件，实际上等价于两个顶点各

一道非常厉害的题目。题意求：\[\sum_{i=0}^{m}c(n,i)\modp\]其中\(c(n,i)\)为无标号第一类斯特林数，且有\(n,m\le10^{18},p\le10^6\)。Sol考虑一个性质：\[x^{\overlinep}\equivx^p-x\modp\]证明比较简单，考虑费马小定理，\(x^p\equivx\modp\)。而\(x,x+1,\cdots,x+

文中符号：\(\operatorname{Period}(s)\)：字符串\(s\)的周期集合。\(\operatorname{Per}(s)\)：字符串\(s\)的最小周期。循环节：\(x\in\operatorname{Period}(s)\)且\(x|\operatorname{len}(S)\)。\(\operatorname{Cyc}(s)\)：\(s\)的最小循环节。\(\operatorname{endpos}(

令原题中的\(1,2,3\)分别对应\(0,1,2\)。一种贪心想法就是直接记录\(0,2,01,21,012/210\)的个数然后直接配对。但是考虑到如果当前的\(1\)前面既有\(0\)也有\(2\)，后面不管是\(0\)还是\(2\)都能配对。但是按照先前的策略肯定会成为\(01\)或\(21\)，这

QOJ#1280.FibonacciPartition（为什么布置的作业题没有任何可见AC记录啊/kk）拿下了QOJ上的用户首杀（同时目前也是QOJ可见的submission中唯一一个过掉这个题的，另一个是vjudge上我的提交）。也许是这个题实在是太冷门了，但是从Fibonacci-Lucas数列的性质应用上是一道非常

QOJ杂题合集QOJ#151.NiceLinesQOJ#838.HorribleCyclesQOJ#894.LongestLooseSegmentQOJ#895.Color给定一个有\(n\)个节点的无向完全图\(G\)，每条边都被染成了\(m\)种颜色中的一种，颜色编号为\(1\simm\)。我们称一个无向完全图合法，当且仅当对于\(\forallx

我们假设目前B知道排列\(p\)的前\(x\)位是多少，那么下一次，B的最优策略是：对于\(i\lex\)的部分，令\(q_i=p_i\)。对于\(i=x+1\)的部分，令\(q_i\)为任一\(p_i\)可能取到但没有被猜过的值。对于\(i>x+1\)，随机乱排剩余的\(q_i\)。考虑设\(c_i\)表示第\(i\)次

令\(a\leb\lec\)。这显然是可以通过交换得到的。考虑若\(a=1\)怎么做。考虑到若把\(b\)或者\(c\)给\(a\)，\(a\)就会翻倍。那就把\(b\)拆成二进制，考虑让\(b\)变为\(0\)。从低位到高位，如果\(b\)这一位为\(1\)就让\(b\)给\(a\)，否则\(c\)给\(a\)。那

考虑当字符串全为\(\texttt{b}\)时，可以通过\(\text{copy}\)\(n-1\)次再\(\text{fuse}\)\(n\)次。这启发从连续段来做，先按顺序构造出一个个连续段，最后\(\text{fuse}\)合为这个串。若第一个连续段为\(\texttt{a}\)，则可以通过\(\text{swap}\)事先交换\(\texttt{ab}

先转化题目条件。发现把\(n\)个点划分为\(2\)个点集，满足其中一个点集存在哈密顿路，另一个点集在补图中存在哈密顿路和原问题是等价的。令直接存在哈密顿路的点集为\(X\)，其路径端点分别为\(S_X,T_X\)；补图中存在哈密顿路的点集为\(Y\)，路径端点分别为\(S_Y,T_Y\);考虑\(

QOJ传送门好题。首先可以视为每一列\(1\)的个数\(\gea_i\)，超出的最后再无视即可。首先先不考虑构造。考虑二分\(k\)，考虑Dilworth定理，即询问是否有\(k\)条链覆盖所有的黑格。可以调整使得第\(i\)条链的起点为\((n-k+i,1)\)，终点为\((i,m)\)。那么一条链往

题面传送门还记得JOISC赛时写了个\(O(n\sqrtn\logn)\)喜提\(28\)分，一直以为这个东西只能根号，这下糗大了（根号直接回滚莫队就行，但是实际上是由log做法的！！考虑离线，然后对于每个点，将这个点到根的路径上的点都染上一个属于这个点的颜色，这样树上每个点所表示的值就是其子树

题面传送门有一个机器人初始在\(A\)点，每次会向左向右随机移动，并给所到位置的\(B\)值\(+1\)，包括起点。当加\(m\)次后停止，设终点为\(t\)，问最后\((t,B)\)二元组总共有多少种可能。\(n\leq10^5,m\leq2\times10^5\)。首先我们需要考虑如何找到一个\((t,B)\)二元组合

题面传送门为啥我会在想多项式做法啊？首先考虑稠密图怎么做，也即\(n=O(\sqrtm)\)的图。将点分为前一半后一半，然后meetinmiddle，其中一边用高维前缀和即可做到\(O(n2^{\frac{n}{2}})\)的复杂度。然后我们需要将其扩展到可能稀疏的图上。仿照三元环计数的方法，将其按照度数排

题面传送门貌似是一个点名被卡的做法，怎么回事呢/cy首先我看到这个东西感觉一脸进制转换，但是这玩意不是非常严格的进制转换，他的某一位的基数是上一位基数乘\(10\)还要\(+1\)，没关系，对于每个数从高到低转化，总能转化出一个合法的进制数。然后考虑调整这个类似进制的数，首先一个比

QOJ传送门考虑\(1\)到其他关键城市的最短路的并是一棵以\(1\)为根的外向树，考虑在外向树上从叶子往根dp。设\(f_{u,i,S}\)为当前在点\(u\)，已经翻修了\(i\)条道路，当前已经经过的关键点集合为\(S\)，最短路最大值的最小值。转移有两种情况，一种是在外向树上往父亲的边

QOJ传送门考虑从低位向高位dp，设\(f_{i,S}\)为考虑到从低到高第\(i\)位，当前每个数超出上界的情况为\(S\)。转移可以枚举这一位填的数：若\(a_j=0,r_j=1\)，那么这一位一定不会超出上界；若\(a_j=1,r_j=0\)，那么这一位一定会超出上界。否则情况和之前相同。容

你细品巨大多太阳的题解，虽然看不懂，但是发现挺有道理的。容易发现，一个无向图是可环覆盖图，当且仅当所有点的度数为偶数。所以将一条边\((u,v)\)看作集合\(\{u,v\}\)，相当于求选出\(i\in[0,m]\)个集合\(\{u_i,v_i\}\)，其对称差为\(\varnothing\)的方案数。考虑集合幂级数，由

题面传送门为什么全场切我不会？为什么全场切我不会？为什么全场切我不会？首先因为题目中要求左括号个数，我们就来关注一下左括号。对于一个左括号，假设它右边是右括号，那么这个左括号就会往右走，否则不会往右走。随便选个左括号开始标号，往左为负，往右为正，设\(p(k,i)\)表示第\(i\)个

题面传送门感觉有点奇妙。首先一个基础的想法就是一个一个往下推，维护每个数往下推的次数，统计当前数在前面的所有数一次归零后会加几次，然后计算这个数需要前面几轮归零，这样将这些系数乘起来就是需要归零的次数了。但是现在有一个问题就是前面每个数往下推的次数可能很大，这东西存

题面传送门设题目中给出的\(1\)的个数占总数的\(\frac{m}{k}\)。考虑一个最朴素的\(O(n^3)\)dp：设\(f_{i,j}\)表示选择了\(i\)个，总和为\(j\)是否存在。当我们用\(j-i\)代替\(j\)的时候显然答案不会被改变，而好处在于可以把\(1\)拉出来单独考虑。当我们不考虑\(1

题面传送门我是傻逼。首先你看这东西长得一脸四元环计数那类东西，于是先给边定向，这样子的话就形成了一张图，每个点只有\(O(\sqrtm)\)条出边。现在我们枚举一个三元环，要计算三个点都指向的点的个数。直接做有\(O(m\sqrtm)\)个三元环，每个三元环需要\(O(\frac{m}{\omega})\)

题面传送门感觉网络流学艺不精，被薄纱了/kk原题意是最少一个点的链，在此基础上最少三个点的链，比较难去用网络流考虑。换个思路：先最大匹配出两点链，然后让最多两点链合并上一个单点变成三点链。这样显然单点最少，并且保证了不会有\(3\)个两点链合并成两个三点链，所以这样是符合题目

题面传送门感觉，非常高妙的随机化！考虑怎么判定一个序列合法，将每种颜色的奇数位置看成左括号，偶数位置看成右括号，则一个序列合法当且仅当其括号序列合法。现在带修，我们维护的东西需要满足如下性质：可逆：将相邻奇数位的信息和偶数位的信息合并需要等于单位元。有结合律：不然没有办