Deep_Dark_FAntasy♂

未归档

Codeforces(3) 博弈论(3) 基本数论、组合数学（排列组合，容斥等）(14) 并查集(2) 数据结构(2) 深度优先搜索、广度优先搜索、搜索剪枝(8) 线性dp、背包问题、区间dp(15) 题解(12)

/ 注册

全部文章 / 未归档（共3篇）

多校1 Hash Function

ai % seed != aj %seed,那么|ai-aj|%seed != 0，|ai-aj|的集合中元素可以用fft组合出来，既然|ai-aj|不能整除seed，同时也说明seed不是任何一个|ai-aj|的因子,因此我们还要筛出每个数的因子,筛因子可以做到O(nlogn) #include ...

FFT

2021-09-01

0 495

快速傅里叶变换和快速数论变换FFT&NTT

快速傅里叶变换(FFT) 作用：加速多项式乘法朴素高精度乘法时间O(n^2),但FFT能O(nlog2n)的时间解决前置知识： 1.点值表示法： f(x)={( x0,f(x0) ),( x1,f(x1) ) ,( x2, f(x2) ), ( x3, f(x3) ), ( x4, f(x4) ...

FFT NTT

2020-10-06

3 706

快速傅里叶变换(FFT)）(复习模板用)

默认n是2的整数幂次。f(x)=a0+a1+...+an-1，比如8，对应的bit就是3，因为只有a0a7，rev[i]是把一个数在二进制下倒过来，思想是把一个数在2进制下分为前bit-1位和最后一位的话，需要让前bit-1位倒过来，并把最后一位放到前面去，由于让rev[i>>1]倒过来...

FFT 数论

2020-07-15

1 671