menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[分治NTT+拆系数FFT+复杂度分析]BZOJ5398【admirable】题解
题目概述有 $n$ 个点的树,现在要覆盖 $K$ 条简单路径,需要满足每条边只能被覆盖 $0,1,K$ 次,求方案数。解题报告这题有毒,CF原题模数是 $998244353$ ,这里强行改成了 ...
[指数型生成函数+分治NTT+广义容斥]LOJ6503(雅礼集训 2018 Day4)【Magic】题解
题目概述有 $n​$ 种颜色的膜法卡,每种颜色有 $a_i​$ 种,总共有 $m​$ 张。现在要把所有卡片排成一排,如果相邻两个卡片颜色相同则产生一个膜法对,求膜法对个数为 $k​$ 的排列个数...
[二维偏序+三维偏序]HHHOJ183【Drinks】题解
解题报告很明显至多选 $3$ 个就能构成一种方案,所以我们只需要考虑选 $1,2,3$ 个的情况就行了。考虑不合法的情况,即物品之间有包含的情况,如:1 1 1 | 3 2 2 2 2 2 | ...
apps HHHOJ
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 条评论
阅读全文
[分治+LCT+二分图判定]Codeforces19E【Fairy】题解
题目概述有 $n$ 个点 $m$ 条边,问有多少边删除了之后让原图是二分图。解题报告远古CF题。删除一条边可以考虑分治,然后用LCT判断有没有奇环就行了。这是斯波做法,时间复杂度 $O(nlog...
apps Codeforces
local_offer 查看标签
comment 0 条评论
阅读全文
keyboard_arrow_up