HDU 6057 Kanade’s convolution$C[k]=\sum_{i \text { and } j=k} A[i\ xor\ j] * B[i \text { or } j]$ 假设$p = i\ or\ j, t = i\ xor\ j$那么有$t \sub p$，其次显然 此时$i\ and\ j = p-t=p\ xor\ t$ $C[k] = \sum_{p\ xor\ t=k} \alpha(p,t)A[t]B[p]$ $\alpha(p,t)$就是对于一对$p , ...

HDU 6036 Division Game考虑每堆石头最多操作$\sum e$次，考虑设$f(x)$表示某一堆石头（最开始都是一样的）操作$x$次后变成了$1$的方案数量。 明显的，某一堆石头操作了$x$次后仍然没有变成$1$的方案数量是$f(x+1)$。因为最后一次操作必然是把石头从某个数字拿到1。（这个算个小trick吧？） 那么对于第$k$堆石头答案就是$f^{k-1}(x+1) f^{m-i+1}(x)$ 因为前$k - 1$堆石头进行了$x$次拿石头的操作还没变成$1$，而从$k$后 ...

hdu 5552 Bus Routes考虑有环的图不方便，可以考虑无环连通图的数量，然后用连通图的数量减去就好了。 无环连通图的个数就是树的个数，又 prufer 序我们知道是$n^{n-2}$其中又由于有$n-1$个边，每个边可以涂色，所以总共无环的方案数量是$m^{n-1} n^{n-2}$ 那么现在就要算连通图的数量了。这个不如不连通图的数量好算。 不连通图的数量怎么算呢，原本想的是容斥，但是貌似不好实现，看了题解发现一种神仙思路。考虑固定一个点，并且让这个点连出一个连通块，剩下的点随意连 ...

HDU 6116 路径计数普通生成函数常用于处理组合问题，指数生成函数常用于处理排列问题。 考虑 对于$a$个$A$分为很多堆，这么分的方案数是$C_{a-1}^{i-1}$ 然后对于每一堆我们看成一个数来放，并且所有堆都这样做，这样的话总的方案数量是$\frac{(i+j+k+l)!}{i!j!k!l!}$ 就算所有一堆看成的数的排列是不存在相邻相等的，至少都有$n-i-j-k-l$对相邻的相同的数。 然后就可以容斥了，枚举$i+j+k+l$直接计算就好了。 $ans = \displayst ...

HDU 5322 Hope考虑$dp[n]$表示 长度为$n$的所有排列的答案。 首先，对于一个排列来说，如果最大值在$i$位置，那么前$i - 1$个数必然与$i$在一个联通块，且必然不会与$i$后面的数字在一个连通块。 那么考虑一种常用的排列的处理技巧，考虑将$n$插入$1 \dots n-1$的一个排列，比如插入的位置是$i$那么$i + 1 \dots n$相当于又是一个排列，而$1 \dots i - 1$的方案数是$A_{n-1}^{i-1}$所以答案就是 $dp[n] = \dis ...

HDU 3516 Tree Construction好久没更博客了 CSP 2019 凉凉。。 这个题看起来就很像区间dp，可以写出 $dp[i][j] = max\{dp[i][k]+dp[k+1][r]+x_{k+1}-x_i+y_k-y_r\}$ 就是考虑$[i,j]$这个区间，其中从$[l,k] , [k + 1 , r]$这两个区间都被构造好了树，然后树的构造大概是 打表发现它满足四边形不等式。 123456789101112131415161718192021222324252 ...

LG 11 月 月赛 II T4看到膜数和$10^5$以及$n^2$的部分分想到很可能是 NTT 于是开始推式子 首先看到式子可以化作， 如果$k = 0$,$f(l , r , k)$为$[l = r]a[l]$ 否则，$f(l , r , k)$为$\displaystyle \sum_{\forall [a,b] \sub [l,r]} f(a,b,k-1)$比较通俗的语言就是对于$[l,r]$的所有子区间求$f(a,b,k-1)$的和。 于是可以考虑对于每一个$a[i]$的贡献，其实 ...

11.7 模拟赛模拟赛鸽了几天没写题解了。。 T1 煎蛋的疑惑考虑每一个左括号表示+1，一个右括号-1，那么画出来的图是这样的 考虑把沿着$x = -m$翻折一下，也就是终点变成了$(2n , -2m)$ 然后假设一次上升为 +1 一次下降为 -1 那么我们相当于是要钦定$n - m$个位置上升，$n + m$个位置下降。那么如果我们钦定$n + m$个位置下降是不是就做完了呢？并不是，然而$n + m$个位置下降仍然会导致一种非法情况 当然这种情况告诉我们，最低点其实是 小于$m$ 而不 ...

10.31 模拟赛A LIS考虑每个数字前从$m$降序构造到$a_i$即可。 1234567891011121314151617181920212223#include <iostream>#include<algorithm>#include<cstring>#include<cstdio>#include<vector>using namespace std;#define MAXN 300006int n , m , k;int ...

随机游走这其实是一个题 给定$n$堆石头每一堆有$a_i$个，每次随机选择仍然有石头的一堆并且从里面拿出一个石头。求期望多少次后第一堆石头不再有石头。第一步是一个结论，原题等价于随机选择一堆石头，如果这堆石头已经没有石头了就重新随机，直到有石头为止。其实这个结论无论是否带权都成立，可以记住。 我们可以对出了第一堆石头外的石头堆分开考虑。假设$E(i)$表示第1堆石头被拿完的时候第$i$堆期望被拿了多少个。一下直接讨论第二堆的情况，其他情况同理。 然后我们可以看成是在生成一个序列，每次有$\fra ...

10.29 模拟赛T1 旅行考虑建立虚点表示上边界和下边界 要求的实际上是上边界到下边界的瓶颈路 于是可以建最小生成树 用kruskal是 mlog 的 所以用$n^2 + m$的prim算法 但是可以不用真正建立出最小生成树，只需要类似最小生成树地跑瓶颈路就可以了 每次更新的时候拿距离最小值来更新。 123456789101112131415161718192021222324252627282930#include<iostream>#include<cstring> ...

10.28 模拟赛A 排列写了一种不知道为啥正确的贪心方法。。 巨难写的正解貌似没啥意义就丢在这里了。 123456789101112131415161718192021222324252627282930313233343536#include<iostream>#include<algorithm>#include<cstring>#include<cstdio>#include<set>using namespace std;#d ...

Comet OJ Contest #13 D$\displaystyle \sum_{i=0}^{\left\lfloor\frac{n}{2}\right\rfloor} a^{i} b^{n-2 i}\left(\begin{array}{c}{n} \\ {2 i}\end{array}\right)$ $T \leq 10^4 , n , m , p \leq 10^{18}$ 注意，由于$p$不一定是质数，而且数据范围看起来很快速幂所有貌似只能快速幂。 这个式子可以化成： $\disp ...

10.25 模拟赛A 闯关对于一个数组，前缀最小值肯定是一段一段得 我们可以考虑一个显然得贪心，每一段最开头从后往前放1，2，3，…，除开最开头的位置直接从前往后放没有放过的。 每一段其实就是一个极长的递增子段。 123456789101112131415161718192021#include <bits/stdc++.h>using namespace std;const int N = 100010;int a[N], b[N];int main() { int n; ...

10.24 模拟赛昨天dls毒瘤虐场今天终于来了一场信心赛。。（但估计明天jls要毒瘤了） A 字符串考虑建出序列自动机，也就是每一个位置指向它之后第一个 0/1 然后直接dp求最短长度，dp的过程可以记搜实现。求答案就再正着做一遍就好了。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include<iostream>#include<algorithm& ...

10.23 模拟赛dls 毒瘤！ T1 爬杆首先，50分很好做，单调栈找找就行了。。后面做法考场胡了个错误的贪心（Orz zzh 会正解） 每个点到全局最小点都得有路。我们可以考虑拿最小点出来递归左右（其实就是笛卡尔树）。 然后还有一个贪心，对于两个点我们想在其中修路，假设小的在左边，大的在右边，那么一定是小的走一段，剩下的都走大的，显然最优。其实第一段之间是不会有其他点的，所以可以看成是全部走的大的。 一个生动形象的例子，如果我们向从第一个梯子到最后一个得到一条路，那么可以这么修： 如果到达 ...

10.22 模拟赛T1 染色考虑每个连通块删成一棵树就好了。 mmp场上就我路径压缩写炸。。。。 1f[1<<21],n,m,t;F(x){t=f[x];return x^t?f[x]=!t?x:F(t):x;}main(s){for(scanf("%*d%d",&s);~scanf("%d%d",&n,&m);f[F(m)]=F(n))s-=F(n)!=F(m);exit(!printf( ...

CF Round 594(Div1) （A~D）简要题解开学基本打不了cf了啊。。 A Ivan the Fool and the Probability Theory对于$1 \times n$的情况，稍微推一推式子发现是斐波那契数列的两倍（因为第一个位置可以是0可以是1，就是两倍了，否则是一倍）。 考虑第一行，第一行有两种情况： 如果第一行是 01010… 交错的，那么 0 开头可以看成一种颜色，1 开头可以看成一种颜色。然后就成了一个竖着的$1 \times n$的情况。然后考虑第 1 ...

CSP-J/S 第一轮知识点选讲转载自这里 感谢原博主的大力整理! 信息学史及基本知识一、信息学及计算机史 计算机的顶级奖项：图灵奖、冯·诺依曼奖 图灵奖：由ACM（美国计算机协会）设立于1966年。是“计算机界的诺贝尔奖”。 冯·诺依曼奖：由IEEE设立。 对信息科学做出突出贡献的大神：图灵（所以才有个奖），冯 · 诺伊曼 中国获图灵奖的大神：姚期智（清华就有姚班，就是以他的名字命名的） 世界第一台电子计算机：埃尼阿克（$ENIAC$），于1946年2月14日（够虐狗的）在美国宾夕法尼亚大 ...

10.17 模拟赛T1直接看题解吧，懒得写了，和前天T2的思路差不多 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495#include<iostream>#include&l ...

10.16 模拟赛T1首先，对于全0或者全1可以手推或者打表发现是卡特兰数。 假设从0切换到1或者1切换到0，一定有$a_i \leq b_i \leq b_{i + 1} \leq a_{i + 1}$ 相当于一定把前$i$个位置填完了才会开始填$i + 1$个位置。 所以直接乘起来就好了。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555 ...

10.15 模拟赛原题场。 A 石子暑假，概率与期望ppt中的经典例题的一道题。。 考虑令$x_i$表示第$i$堆石头在第几次被取。那么有 $x_1 = \sum_i{ [x_i \leq x_1] } = 1 + \sum_i{[x_i < x_1]}$ 两边同时套一个期望，由期望的线性性 $E(x_i) = 1 + \sum_iE([x_i < x_1]) = 1 + \sum_i{P([x_i < x_1])}$ 然后求的就是第$i$堆石头比第一堆石头先取的概率。 这个可 ...

10.14 模拟赛抱歉咕了一天，前一天晚自习搞oj去了。 A 序列开始看错题了1h20分钟。。。。一场爆炸。。 枚举开头是0还是1，就已经确定了每个数字到哪里（这个贪心显然） 然后我们考虑怎样让字典序变小，我们注意到只有同往一个方向走，且可以第一次的可以覆盖第二次的起点的时候可以任意交换。可以拿一个set或者pq维护一下。 真的毒瘤。。 12345678910111213141516171819202122232425262728293031323334353637383940414243444 ...

10.12 模拟赛T1首先有一个显然可以得到的结论，每次减去最大值一定最优。 只会最无脑的做法。。每次减去最大值，复杂度$O(n)$，虽然减了一些枝但还是显然过不去 其实感觉60分做法就很有意思了。 对于$n \leq 10^{12}$ 考虑分开考虑前六位和后六位，这个时候前六位的变化只有$O(\sqrt n)$次。 考虑当前六位的最大值为某一个值时，后六位分别需要多少次才可以变成负数，以及会变成多少 复杂度是$O(\sqrt n)$ 对于$n \leq 10^{18}$ 也是一个挺奇妙的搞法吧 ...

Peaks ( Gym 100365H )这题nk做法还挺正常的。。后面那个循环就很恶心了 考虑 dp[i][j] 表示长度为i的排列，恰好有k个峰的方案数量。 然后转移就是把 i 插入 i-1 的排列。 i显然是i-1的排列里面最大的数，然后插入就只有两种情况： 插入在峰的左右，由于峰不可能相邻，所以可以插入在 2j 个位置 插入在爬山的时候，那么峰的数量+1 $dp[i][j] = 2j\times dp[i-1][j] + ( i - 2(j - 1) )dp[i-1][j-1]$ 其 ...

一种优化方法，具体例子可以看这里 这里只是存一下手写Bitset的板子 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091struct Bitset{ unsigned a[1600]; voi ...

Sums gym100753M同余最短路模板，然而这个东西貌似也可以做去年D1T2 首先我们选择一个模数作为基准，然后剩下的这样连边： 对于一个面值为 x 的硬币 ，当前在 u 这个点（感性理解一下吧） u + x < Mod 这种情况直接从u向 u + x 连一条长度为0的边，表示我们在 0 * M + (u + x) 的时候就已经可以凑出了 u + x > Mod 这种情况下可以 u 向 ( u + x ) mod Mod 连一条长度为1的边，表示通过x的硬币至少在 1 * ...

Break upCF700C 首先考虑只能删一条边的做法，我们可以找出所有的桥，然后随便跑一条 S 到 T 路径，如果这条路径上有桥就说明可以，否则不行 发现这个做法其实是 O(M) 的 那么可以先随便找一条 N 到 M 的路径，分别尝试删这条路径上的边再套上面做法就好了。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606 ...

Cycling City毒瘤题 首先建dfs树，由于是个无向图所有返祖边都是连向祖先的。 判是否有解其实很简单，只要图不是一个仙人掌就有解了。 仙人掌有关可以看这个博客 但是这道题由于要输出路径成功变成了一个一个顶俩的题。。。。。 通过判仙人掌我们确认了一个点，它连向自己父亲的路径至少被两个边所覆盖。 然后我们可以从这个点开始深搜，找到这两个返祖，注意是返向这个点祖先的路径。 于是有起点就是这两个路径下端的lca，终点就是这两个路径上端点最深的一个（画图很好看出来的） 然后有哪些路径就显然了。。 ...

Unique PathAGC 038 D 考虑如果两个点之间只能有一个边它们就把它们缩起来，那么最后缩起来的每一块都只能是一棵树。 如果两个点之间必须不止一个边，并且在一个连通块，显然无解。 首先把所有树给连好，现在的可用的边的数量只有$m - n + c$了。 然后两个连通块之间如果有超过一条边，连通块内部的点显然不只一条路径了。 其他情况，如果我们给连通块连边的时候每个连通块都只一直用一个点来往外连，就可以保证所有连通块都满足要求。 如果不存在两个点之间不只一个边的情况 那么只要可用的边的 ...