zcmimi's blog

arrow_back高精度共6篇文章

avatar
zcmimi
2020-02-27

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

前置知识:

  1. FFT

  2. 原根

原根的性质

p是质数,g为模p的原根,n|(p-1),$g_n=g^{(

avatar
zcmimi
2020-02-25

FFT

fst fst tle

DFT: 离散傅里叶变换

IDFT: 离散傅里叶逆变换

FFT: 快速傅里叶变换

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

FWT: 快速沃尔什变换,利用类似FFT的东西解决一类卷积问题

MTT: 毛爷爷的FFT,非常nb/任意模数

FMT: 快速莫比乌斯变化

(摘自https://www.cnblogs.com/zwfymqz/p/8244902.html)

为什么要用到FFT呢?

以高精度乘法举个例子:

你现在要计算a\times b,a,b>10^{1000000}

len_a=n,len_b=m

如果用普通的高精度乘法\mathcal{O(nm)},直接tle

但是FFT可以做到\mathcal{O((n+m) \log (n+m))}

原理: 先把多项式转化为用点值表示\mathcal{O(n \log n)}

然后再用点值相乘来计算\mathcal{O(n)}

然后再通过点值还原多项式

avatar
zc
2020-10-22 10:06:14

查看原题

点击跳转

根据平方和公式可以发现分越多段越好

而进一步又可以发现最后一段的总和越小越好

以下是88分代码(高精什么的懒得写了):

avatar
zc
2020-02-07 13:50:00
查看原题

点击跳转

  1. 金神石的块数必须是6的倍数 g(x)=1+x^6+x^{12}+...=\frac 1{1-x^6}
  2. 木神石最多用9块 g(x)=1+x+x^2+...+x^9=\frac{1-x^{10}}{1-x}
  3. 水神石最多用5块 g(x)=1+x+x^2+...+x^5=\frac{1-x^6}{1-x}
  4. 火神石的块数必须是4的倍数 g(x)=1+x^4+x^8+...=\frac 1{1-x^4}
  5. 土神石最多用7块 g(x)=1+x+x^2+...+x^7=\frac{1-x^8}{1-x}

  6. 金神石的块数必须是2的倍数 g(x)=1+x^2+x^4+...=\frac 1{1-x^2}

  7. 木神石最多用1块 g(x)=1+x=\frac{1-x^2}{1-x}
  8. 水神石的块数必须是8的倍数 g(x)=1+x^8+x^{16}+...=\frac 1{1-x^8}
  9. 火神石的块数必须是10的倍数 g(x)=1+x^{10}+x^{20}+...=\frac 1{1-x^{10}}
  10. 土神石最多用3块 g(x)=1+x+x^2+x^3=\frac{1-x^4}{1-x}

\frac 1{1-x^6}\cdot\frac{1-x^{10}}{1-x}\cdot\frac{1-x^6}{1-x}\cdot\frac 1{1-x^4}\cdot\frac{1-x^8}{1-x}\cdot\frac 1{1-x^2}\cdot\frac{1-x^2}{1-x}\cdot\frac 1{1-x^8}\cdot\frac 1{1-x^{10}}\cdot\frac{1-x^4}{1-x}

=\frac1{(1-x)^5}

=\sum_{i=0}^\infty {i+4 \choose 4}x^i

\sum_{i=0}^\infty {i+k-1 \choose k-1}x^i=\frac1{(1-x)^k}

n项的系数是{n+4 \choose 4}需要FFT或NTT

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

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

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

n = x^x \mod 1000

这样相当于在n-1个空位中插k-1块隔板

\therefore ans = C(n-1,k-1)

\because k \le 100,n\le 1000

\therefore我们用杨辉三角(用滚动数组,否则可能re)就可以了,但是要高精度

当然如果直接计算组合数更快

杨辉三角版:

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

思路剧毒无比

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

f[i][j] = \max(f[i][k] \times f[to][j-k])

f[i][0] = \max(f[i][0],f[i][j] \times j)

还没完

吐血的是还要写高精

1/1
Search
search