Fizzmy

FFT

--------DP--------(1) CDQ分治(1) DP(11) z-box(6) 主席树(1) 二分(2) 分数规划(1) 分治(1) 区间DP(3) 博弈论(2) 后缀数组(2) 哈希(1) 学习笔记(2) 容斥(1) 并查集(4) 强连通分量(1) 扫描线(1) 数位DP(3) 数论(12) 斯特林数(1) 暴力(2) 最小生成树(1) 最短路(1) 期望DP(4) 未归档(5) 树形dp(4) 模拟(1) 模板(3) 游记(1) 状态压缩(8) 线段树(12) 组合数学(1) 网络流(4) 脑洞(8) 莫比乌斯反演(2) 贡献法(3) 题解(2)

/ 注册

全部文章 / FFT （共4篇）

BZOJ2194: 快速傅立叶之二-FFT

题意：给出a,b,计算 C[k]=∑n−1i=ka[i]∗b[i−k] C [ k ] = ∑ i = k n − 1 a [ i ] ∗ b [ i − k ] , n<=1e5 n <= 1 e 5 Solution: 回想多项式乘法： ∑2n−2k=0(∑k=i+ja...

2021-08-18

0 353

bzoj3527:[Zjoi2014]力-FFT

传送门题意：给出n个数 qi q i ,F和E的定义如下： Fj=∑i<jqiqj(i−j)2−∑i>jqiqj(i−j)2 F j = ∑ i < j q i q j ( i − j ) 2 − ∑ i > j q i q j ( i − j ) 2 ...

2021-08-18

0 506

BZOJ2459:残缺的字符串-FFT

权限题题意：有两个仅包含小写字母的字符串A和B，其中A串长度为m，B串长度为n。这两个串已经老化了，每个串都有不同程度的残缺。你想对这两个串重新进行匹配，其中A为模板串，那么现在问题来了，请回答，对于B的每一个位置i，从这个位置开始连续m个字符形成的子串是否可能与A串完全匹配? 1&...

2021-08-18

0 223

BZOJ5093: [Lydsy1711月赛]图的价值-斯特林数+FFT

传送门题意： “简单无向图”是指无重边、无自环的无向图（不一定连通）。一个带标号的图的价值定义为每个点度数的k次方的和。给定n和k，请计算所有n个点的带标号的简单无向图的价值之和。因为答案很大，请对998244353取模输出。 1≤n≤109,1≤k≤200000 1 ≤ n...

2021-08-18

0 293