zcmimi's blog

arrow_backntt共9篇文章

avatar
zcmimi
2020-08-27 22:46:00
avatar
zcmimi
2020-02-27

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

前置知识:

  1. FFT

  2. 原根

原根的性质

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

avatar
zc
2020-09-15 20:16:00
查看原题

点击跳转

g(n)为点数为n的无向图个数

g(n)=2^{n\choose 2}

f(n)为点数为n的简单无向连通图的数量

枚举连通块个数i可得

\displaystyle g(n)=\sum_{i=0}^n \frac{f(i)}{i!}

发现这个形式很眼熟(生成函数):

g=e^f

那么f=\ln g

求出g\ln就可以得到f

avatar
zc
2020-07-18 11:27:00
查看原题

点击跳转

avatar
zc
2020-07-07 17:25:00
查看原题

点击跳转

首先了解原根

这里利用到原根的一个性质:

gm的一个原根
g^0,g^1,g^2,\dots,g^{\varphi(m)-1}构成模m的简化剩余系

这样我们可以把序列中所有数变成原根的次幂,

那么序列中所有数的乘积就可以转化为他们的和

设这个和为sum

设生成函数:\displaystyle f(x)=\sum_{i=0}^m [i\in S]x^i

可以发现f(x)^n次数为sum的那一项的系数就是答案

使用快速幂+快速数论变换

avatar
zc
2020-07-05 13:10:00
查看原题

点击跳转

首先找位置对称的回文子序列个数(多项式求)

由于不能连续,所以减去对称回文子串个数(manacher求)

设字符串为S,|S|=n

假设S_i作为一个子序列的对称中心,x=\sum_{j=1\le j\le i-1}[S_{i-j}=S_{i+j}]

那么以i为中心位置的方案数为2^{x+1}-1

A_i=[S_i=a],B_i=[S_i=b]

那么\displaystyle (A*A)_i=A_i*A_i=\sum_{j=0}^nA_jA_{i-j}就是对称中心为位置\frac i2的两端为a的数量

同理(B*B)_i就是对称中心为位置\frac i2的两端为b的数量

那么上述(A*A)_i+(B*B)_i就是对称中心为位置\frac i2x+1

如果i为偶数,x+1要减去1(对称中心是否在同个字符上)

avatar
zc
2020-03-08 15:07:00
查看原题

点击跳转

avatar
zc
2020-02-08 22:00:00
查看原题

点击跳转

假设我们要求的是A\cdot B \equiv 1 \pmod{x^n},

我们已经求出了B'满足A\cdot B' \equiv 1 \pmod{x^\frac n2}

\because A\cdot B \equiv 1 \pmod {x^n} \\ \because A\cdot B' \equiv 1 \pmod{x^\frac n2} \\ \therefore A \cdot (B-B') \equiv 0 \pmod{x^\frac n2} \\ \therefore B-B' \equiv 0 \pmod{x^\frac n2} \\ (B-B')^2 \equiv 0 \pmod{x^n} \\ B^2-2BB'+B'^2 \equiv 0 \pmod{x^n} \\ \therefore A(B^2-2BB'+B'^2) \equiv 0 \pmod{x^n} \\ AB^2-2ABB'+AB'^2 \equiv 0 \pmod{x^n} \\ \because A\cdot B \equiv 1 \pmod {x^n} \\ \therefore B-2B'+AB'^2\equiv 0 \pmod{x^n} \\ B\equiv 2B'-AB'^2 \pmod{x^n}

于是我们可以用倍增+NTT解决(复杂度\mathcal{O(n \log^2 n)})

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

1/1
Search
search