menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[BSGS+矩阵求逆]BZOJ4128【Matrix】题解
题目概述给出矩阵 $A,B$ ,求最小的 $x$ 满足 $A^x\equiv B(mod\ p)$ 。解题报告哇 $A^x\equiv B(mod\ p)$ ,上BSGS!枚举 $A^{im}A...
apps BZOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[三元环计数]HDU6184【Counting Stars】题解
题目概述给出一张无向图,求 $4$ 个点构成两个有公共边的三元环的方案数。解题报告填坑填坑,如果我们知道每条边所在的三元环个数 $num_i$ ,那么 $\sum_{i=1}^{m}{num_i...
apps HDU
local_offer 查看标签
comment 0 条评论
阅读全文
[伯努利数+拆系数FFT+多项式求逆]51Nod1258【序列求和 V4】题解
题目概述求 $\sum_{i=1}^{n}i^K,K\le 50000$ 。解题报告同51Nod1228,只不过 $K\le 50000$ 所以不能 $O(K^2)$ 处理伯努利数,于是我们根据...
[伯努利数]51Nod1228【序列求和】题解
题目概述求 $\sum_{i=1}^{n}i^K$ 。解题报告这个东西可以用二项式定理和组合数 $O(n^2)$ 递推来着,但是 $n$ 太tm大了,不过 $K$ 很小,所以要想办法搞成只和 $...
local_offer 查看标签
comment 0 条评论
阅读全文
[FMT]WC2018【州区划分】题解
解题报告搜FMT搜到这道题,其实我都想到怎么做了……结果以为自己解法是错的就没写了……FMT除了集合并卷积之外还有一个经典应用就是子集卷积,他是这样的:$$ h_s=\sum_{A\subset...
apps 洛谷
local_offer 查看标签
comment 0 条评论
阅读全文
[FMT]BZOJ4036(HAOI2015)【按位或】题解
题目概述刚开始 $x$ 为 $0$ ,每秒会产生一个 $[0,2^n)$ 的随机整数使 $x$ 或上这个数,生成 $i$ 的概率为 $p_i$ ,问 $x$ 变成 $2^n-1$ 的期望时间。解...
local_offer 查看标签
comment 0 条评论
阅读全文
[cdq分治+NTT]洛谷4721【分治 FFT】题解
题目概述给出 $g$ 以及 $f(0)=1$ ,求:$f(i)=\sum_{j=1}^{i}f(i-j)g(j)$ 。解题报告其实我是想学分治+NTT来着的,结果搜分治FFT就搜到这个了,于是填...
apps 洛谷
local_offer 查看标签
comment 0 条评论
阅读全文
[贪心]NOIP2018Day2【旅行】题解
解题报告树的情况直接贪心做,基环树枚举环上的边断开然后贪心做。乱优化代码害人不浅,少 $20$ 分送我爆炸。测评鸭上面有 $O(n)$ 加强版,大佬们可以去切啊QAQ。示例程序#include&...
apps LOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[矩阵树定理]BZOJ4894【天赋】题解
题目概述有 $n$ 个技能,每个技能有一些前置技能,现在 $1$ 技能已学习,求学完所有技能的方案数。解题报告矩阵树定理求有向图中外向树和内向树的个数:外向树:边从父亲到儿子的有向树度数矩阵为每...
apps BZOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[莫比乌斯函数+线性筛]BZOJ3309【DZY Loves Math】题解
题目概述令 $f(x)$ 表示 $x$ 质因数分解之后最大的次幂,$m$ 次询问,每次求 $\sum_{i=1}^{A}\sum_{j=1}^{B}f[(i,j)]$ 。解题报告先正常操作一下:...
keyboard_arrow_up