链接:lg1919
题解
简单FFT模板,将n位数分解为$a_0+a_1 \* x+a_2 \* x^2+...+a_{n-1} \* x^{n-1}$,
$a_j=\frac{1}{n} \sum_{k=0}^{n-1} y_k\omega_n^{-kj}$
$$dp[i]=i^n-\sum_{j=1}^{i-1}{C_i^j*dp[j]}$$
FFT
1 |
|
NTT
1 |
|
learn
链接:lg1919
简单FFT模板,将n位数分解为$a_0+a_1 \* x+a_2 \* x^2+...+a_{n-1} \* x^{n-1}$,
$a_j=\frac{1}{n} \sum_{k=0}^{n-1} y_k\omega_n^{-kj}$
$$dp[i]=i^n-\sum_{j=1}^{i-1}{C_i^j*dp[j]}$$
1 | #include<bits/stdc++.h> |
1 | #include<bits/stdc++.h> |