复习长链剖分。

首先划分长链,走到每个长链顶就给这个长链开个数组拿来记答案,数组的长度(从0开始算)是整个长链上点的个数,下标为k的位置所表示的意义是到长链顶距离为k的点的个数,沿着重链走的时候,直接指针偏移一位就行了(毕竟状态在深度上连续)。

然后DFS,走到每一个点,先给这个点的DP数组指针(设为arr),下标为0的位置加个1,表示这个点自己的答案。然后如果这个点有重子节点,就先沿着重子节点走,走的时候DP数组直接偏移上1,然后这个点的答案先记录为重子节点的答案+1(我们要考虑所有子节点的答案,一会拿这玩意来更新)。

对于非重子节点的点,开个新的DP数组,然后直接传下去往下递归。

非重子节点返回后尝试更新答案。枚举非重子节点DP数组上的每一个状态,把他的值加到当前节点的DP值上(即合并子链状态,把状态合并到重链上),然后顺带更新一波结果(如果某个深度的值出现的比当前的多,就直接更新,如果相当就比一下深度),合并晚状态后直接把非重子节点的内存回收掉即可。

显然复杂度是$\theta(n)$的,每条重链会有一个DP数组,这个DP数组的长度是重链的长度,每条重链的答案只会被合并一次,而所有重链的长度之和是$n$。

#include
阅读全文..

傻逼HDU

原题内存1G,贵题内存128M,真的nb

傻逼题,先对于一个点i,枚举所有点j,然后计算i和j构成的直线的斜率,记在i的map里(即对于每个点i,统计i作为线段一个端点的情况下,不同的斜率取值所对应的点的个数)

然后对于每个询问,分$A_i$是直角端点和非直角端点的情况讨论。

$A_i$是直角端点的情况下,枚举下n个点,算出来斜率的取值情况然后存起来。然后再枚举一个点,钦定这是第一条直角边,然后算出来另一条直角边的斜率,去刚刚存的map里反查有多少种情况,最后除个2(一种情况会被算两次)

$A_i$不是直角端点的情况下,枚举一个点,连起来构成一条直角边,然后算一下另一条直角边的斜率,然后去一开始预处理的数组里去查下能有多少种即可。(这个不需要除2,因为不会算重)

如何存斜率?别用浮点数,写个有理数类。如何记斜率不存在?分母写0,分子写1(分子不要写别的数,不方便统计)。如何记斜率为0?分子写1,分母写0。

另外为了统计方便,我们所存储的有理数均为最简分数,并且正负号全都在分子上(0和不存在除外,这时不需要考虑符号)

要做直接去CF交吧,HDU太傻逼了。

要用unordered_map并且自己写个hasher,map太慢了。

https://codeforces.com/gym/102361/problem/A

#include
阅读全文..

众所周知,这题不是个人也会。

$$ \text{首先可知}d\left( nm \right) =\sum_{a|n}{\sum_{b|m}{\left[ \mathrm{gcd}\left( a,b \right) =1 \right]}} \\ \sum_{1\le i\le n}{\sum_{1\le j\le m}{\sum_{a|i}{\sum_{b|j}{\left[ \mathrm{gcd}\left( a,b \right) =1 \right]}}}} \\ =\sum_{1\le i\le n}{\sum_{1\le j\le m}{\sum_{a|i}{\sum_{b|j}{\sum_{k|gcd\left( a,b \right)}{\mu \left( k \right)}}}}} \\ =\sum_{1\le k\le n}{\mu \left( k \right) \sum_{1\le i\le n}{\sum_{1\le j\le m}{\sum_{a|i}{\sum_{b|j}{\left[ k|\mathrm{gcd}\left( a,b \right) \right]}}}}} \\ =\sum_{1\le k\le n}{\mu \left( k \right) \sum_{1\le a\le n}{\sum_{1\le b\le m}{\sum_{a|i,i\le n}{\sum_{b|j,j\le m}{\left[ k|gcd\left( a,b \right) \right]}}}}} \\ a\gets ak,b\gets bk \\ =\sum_{1\le k\le n}{\mu \left( k \right) \sum_{1\le ak\le n}{\sum_{1\le bk\le m}{\left[ k|gcd\left( ak,bk \right) \right] \lfloor \frac{n}{ak} \rfloor \lfloor \frac{m}{bk} \rfloor}}} \\ =\sum_{1\le k\le n}{\mu \left( k \right) \sum_{1\le a\le \lfloor \frac{n}{k} \rfloor}{\sum_{1\le b\le \lfloor \frac{m}{k} \rfloor}{\lfloor \frac{n}{ak} \rfloor \lfloor \frac{m}{bk} \rfloor}}} \\ =\sum_{1\le k\le n}{\mu \left( k \right) \sum_{1\le a\le \lfloor \frac{n}{k} \rfloor}{\sum_{1\le b\le \lfloor \frac{m}{k} \rfloor}{\lfloor \frac{\lfloor \frac{n}{k} \rfloor}{a} \rfloor \lfloor \frac{\lfloor \frac{m}{k} \rfloor}{b} \rfloor}}} \\ =\sum_{1\le k\le n}{\mu \left( k \right) \left( \sum_{1\le a\le \lfloor \frac{n}{k} \rfloor}{\lfloor \frac{\lfloor \frac{n}{k} \rfloor}{a} \rfloor} \right) \left( \sum_{1\le b\le \lfloor \frac{m}{k} \rfloor}{\lfloor \frac{\lfloor \frac{m}{k} \rfloor}{b} \rfloor} \right)} \\ S\left( n \right) =\sum_{1\le i\le n}{\lfloor \frac{n}{i} \rfloor} \\ \text{原式}=\sum_{1\le k\le n}{\mu \left( k \right) S\left( \lfloor \frac{n}{k} \rfloor \right) S\left( \lfloor \frac{m}{k} \rfloor \right)} \\ $$

#include
阅读全文..

众所周知,这题是个人就会。

$$ \text{钦定}N\le M \\ \sum_{1\le i\le N}{\sum_{1\le j\le M}{\left[ \mathrm{gcd}\left( i,j \right) =p \right]}} \\ \sum_p{\sum_{1\le pi\le N}{\sum_{1\le pj\le M}{\left[ \mathrm{gcd}\left( pi,pj \right) =p \right]}}} \\ \sum_p{\sum_{1\le i\le \lfloor \frac{N}{p} \rfloor}{\sum_{1\le j\le \lfloor \frac{M}{p} \rfloor}{\left[ \mathrm{gcd}\left( i,j \right) =1 \right]}}} \\ \sum_p{\sum_{1\le i\le \lfloor \frac{N}{p} \rfloor}{\sum_{1\le j\le \lfloor \frac{M}{p} \rfloor}{\sum_{k|gcd\left( i,j \right)}{\mu \left( k \right)}}}} \\ \sum_p{\sum_{1\le k\le \lfloor \frac{N}{p} \rfloor}{\sum_{1\le ik\le \lfloor \frac{N}{p} \rfloor}{\sum_{1\le jk\le \lfloor \frac{M}{p} \rfloor}{\sum_{k|gcd\left( ik,jk \right)}{\mu \left( k \right)}}}}} \\ \sum_p{\sum_{1\le k\le \lfloor \frac{N}{p} \rfloor}{\sum_{1\le i\le \lfloor \frac{N}{kp} \rfloor}{\sum_{1\le j\le \lfloor \frac{M}{kp} \rfloor}{\mu \left( k \right)}}}} \\ \sum_{1\le p\le N,p\,\,is\,\,prime}{\sum_{1\le k\le \lfloor \frac{N}{p} \rfloor}{\mu \left( k \right) \lfloor \frac{N}{kp} \rfloor \lfloor \frac{M}{kp} \rfloor}} \\ T=kp \\ T\le N \\ \sum_{1\le T\le N}{\sum_{p|T\left( T\text{的所有质因数} \right)}{\lfloor \frac{N}{T} \rfloor \lfloor \frac{M}{T} \rfloor \mu \left( \frac{T}{p} \right)}} \\ =\sum_{1\le T\le N}{\lfloor \frac{N}{T} \rfloor \lfloor \frac{M}{T} \rfloor \sum_{p|T,\left( T\text{的所有质因数} \right)}{\mu \left( \frac{T}{p} \right)}} $$

#include
阅读全文..

简单复习了以下AC自动机。

首先注意,$$n$$个字符串构建的AC自动机至多可能有总串长+1个节点(根节点不隶属于任何一个字符串)

由fail指针构成的树叫做后缀链接树,每个点的父节点为这个点所表示的字符串,在整个ACAM里能匹配到的公共后缀最长的字符串。(与SAM里的后缀连接好像是一样的....)

构建后缀链接,并且把Trie树补成Trie图(即将每个点的不存在的子节点指向下一个待匹配位置的操作)通过BFS进行。

初始时: 根节点的子节点的fail指针全都指向根,根节点的不存在的子节点构造关于根的自环。

接下来根节点的存在的子节点入队,开始BFS。

从队列里取出来队首元素V,按照如下方法操作:

遍历其子节点,设当前遍历到的子节点通过字符chr获得,如果这个子节点存在,则其后缀链接指向V的后缀链接指向的节点的chr子节点,并将该节点入队。

如果该子节点不存在,则将其替换为V的后缀链接的chr子节点。

如果遇到一个所有字符串都没出现的字符怎么办?这时我们肯定会走到根,然后沿着根节点的子节点走自环,成功滚到下一个字符。

匹配时直接沿着Trie图走即可(我们在BFS中已经把所有点的子节点补完了),每走到一个点,则说明了我们匹配到了根到这个点的边所构成的字符串。

然后怎么统计每个子串出现的次数呢?

首先我们在ACAM上的每个点标记上以这个点结尾的字符串,可以知道这种标记只会有总字符串个数个。

然后我们构建出后缀链接树,我们可以知道,当我们的字符串走到某个点的时候,就意味着匹配到了这个点在后缀链接树上到树根经历的所有字符串,然后我们打个到根的差分标记,最后DFS统计下标记即可求出来每个字符串访问了几遍。

#include
阅读全文..

/px

被卡读入,自毙。

按照下标分块,令块大小为$N$,则对于每一组询问$(x,y)$,当$x\geq N$时直接暴力枚举所有符合要求的点$xk+y$(不会超过$N$个);

对于$x<N$的情况,我们维护一个二维数组$arr[x][y]$,表示$arr[x][y]$的答案,回答时直接输出即可。

对于修改操作,我们直接枚举所有不超过$N$的数,分别取模后修改数组即可。

#include
阅读全文..

$$ \text{对于矩阵}M,\text{构造其特征多项式}G\left( x \right) \\ \text{则有}M^n=G\left( M \right) Q\left( M \right) +R\left( M \right) \\ \text{即}M^n\equiv R\left( M \right) \left( mod\,\,G\left( M \right) \right) \\ \text{即}x^n\equiv R\left( x \right) \left( \text{mod }G\left( x \right) \right) \\ \text{考虑特征多项式如何计算。} \\ G\left( x \right) =\det \left( M-x\text{I} \right) ,\text{其中}I\text{为单位矩阵} \\ \text{由于}G\left( x \right) \text{为}n\text{次多项式}\left( n\text{为矩阵大小} \right) ,\text{故可以通过插值求出来对应的特征多项式。} \\
\\ \text{然后多项式快速幂}+\text{取模即可} $$

#include
阅读全文..