by ·0评论

复习长链剖分。

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

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

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

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

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

#include
阅读全文..

by ·一条评论

傻逼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
阅读全文..

by ·0评论

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

$$ \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
阅读全文..

by ·0评论

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

$$ \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
阅读全文..

by ·0评论

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

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

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

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

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

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

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

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

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

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

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

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

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

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

#include
阅读全文..

by ·0评论

/px

被卡读入，自毙。

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

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

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

#include
阅读全文..

by ·0评论

$$ \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
阅读全文..