知識總結 多項式全家桶(四)(快速冪和開根)

2022-09-22 09:23:00 字數 2756 閱讀 5710

推薦小恐龍的部落格(參考資料):多項式開根

(本文中一切多項式運算預設在模 \(x_n\) 意義下進行)

多項式快速冪?首先有一種很顯然的方式是把整數快速冪裡面的整數乘法替換成多項式乘法 ntt ,複雜度 \(o(n\log^2n)\) 。

然而還有一種 \(o(n\log n)\) 的做法:要求 \(b=a^k\) ,相當於求 \(\log_a b=k\) ,用換底公式得 \(\log_a b=\frac=k\) ,所以 \(b=e^\) 。

然後寫個多項式對數函式和指數函式(參見【知識總結】多項式全家桶(二)(ln和exp) )就完了。

注意,多項式運算是對 \(x^n\) 取模而不是對 \(998244353\) 取模!對質數取模僅僅是為了避免出現高精度或小數,對多項式運算沒有任何影響。所以不要像我一樣傻以為指數上要對 \(998244352\) 取模 qaq 。

**:

#include #include #include #include #include using namespace std;

namespace zyt

templateinline void write(t x)

typedef long long ll;

const int n = 1e5 + 10, p = 998244353, g = 3;

inline int power(int a, int b)

return ans;

} inline int get_inv(const int a)

namespace polynomial

for (int i = 0; i < n; i++)

rev[i] = ((rev[i >> 1] >> 1) | ((i & 1) << (lg2 - 1)));

} void ntt(int *a, const int *w, const int n)

}void mul(const int *a, const int *b, int *c, const int n)

void _inv(const int *a, int *b, const int n)

}void inv(const int *a, int *b, const int n)

void derivative(const int *a, int *b, const int n)

void integrate(const int *a, int *b, const int n)

void ln(const int *a, int *b, const int n)

void _exp(const int *a, int *b, const int n)

}void exp(const int *a, int *b, const int n)

}int work() }

int main()

首先當然可以直接用上面的快速冪,相當於計算 \(k\) 是 \(2\) 的逆元時的情況。但有一種常數更小也更好寫的方法:

求 \(b=\sqrt a\) ,即 \(b^2=a\) 。和求逆、求指數函式類似,採用分治的思想。假設已經求出 \(b_0\) 滿足 \(b_0^2=a \mod x^\rceil}\) ,求 \(b^2=a\mod x^n\) 。

顯然有 \(b^2=a \mod x^\rceil}\) ,所以 \(b_0-b=0 \mod x^\rceil}\) 。

類似求逆,兩邊同時平方,得到:

\[(b_0-b)^2=0 \mod x^n

\]展開,得到:

\[b_0^2-2b_0b+b^2=0 \mod x^n

\]即:

\[b_0^2-2b_0b+a=0 \mod x^n

\]移項:

\[b=\frac \mod x^n

\]多項式求逆即可。

**:

#include #include #include #include using namespace std;

namespace zyt

templateinline void write(t x)

typedef long long ll;

const int n = 1e5 + 10, p = 998244353, g = 3;

inline int power(int a, int b)

return ans;

} inline int get_inv(const int a)

namespace polynomial

for (int i = 0; i < n; i++)

rev[i] = ((rev[i >> 1] >> 1) | ((i & 1) << (lg2 - 1)));

} void ntt(int *a, const int *w, const int n)

}void mul(const int *a, const int *b, int *c, const int n)

void _inv(const int *a, int *b, const int n)

}void inv(const int *a, int *b, const int n)

void _sqrt(const int *a, int *b, const int n)

}void sqrt(const int *a, int *b, const int n)

}int n, a[n << 2];

int work() }

int main()