menu zcmimi's blog

arrow_back 高精度

NTT基本上跟FFT一样,就是把单位根换成了原根(原根和单位根一样具有FFT需要的特殊性质)

前置知识:

  1. FFT(这里就不讲了)

  2. 原根

原根

阶:

zcmimi
2020-02-27

FFT

fst fst tle

DFT: 离散傅里叶变换

IDFT: 离散傅里叶逆变换

FFT: 快速傅里叶变换

FNTT/NTT: 快速傅里叶变换的优化

zcmimi
2020-02-25
  1. 金神石的块数必须是6的倍数 g(x)=1+x^6+x^{12}+...=\frac 1{1-x^6}
  2. 木神石最多用9块 $g(x)=1+x+x^2+...+x^9=\fra
zc
2020-02-07 13:50

思路剧毒无比

f[i][j]表示在i的子树中,i所在的连体块大小为j\frac{\text{最大得分}}{j}

$f[i][j] = \max(f[i][k] \times

zc
2019-12-21 19:47

\sum_{i=1}^k a_i = x^x \mod 1000 (a_i \in \N^*)

\because 总和一定为x^x \mod 1000,并且分为k个数,

设$n

zc
2019-12-21 19:47
1 / 1
Search
search