总结
今天是数学专题啊，内容还有一点多。勇敢牛牛，不怕困难！虽然看着有点恐怖，但是看着还好。
不定方程
这个知识点比较简单，上一道例题。
[HNOI2002] 跳蚤 想一下突然发现这道题很反演呢？那就归到后面一类吧嘻嘻。就是要求 \(n\) 个数 gcd 为 1 的数量用 \(f_m\) 表示，另外设 \(g_m=m^n\)，然后很容易列出两个的关系莫比乌斯反演就可以，为了节省题目，这里面求莫比乌斯函数我直接用杜教筛嘻嘻，直接切掉今天三个板块。
莫比乌斯反演
[HNOI2002] 跳蚤 为什么又是你？
杜教筛
[HNOI2002] 跳蚤 怎么还是你？（其实有一点牵强，我XX）顺便提一嘴，昨天晚上床上想了一下杜教筛的推导过程，发现自己竟然轻松想出来了，感觉很兴奋，哇酷哇酷。
中国剩余定理
【模板】扩展中国剩余定理 打过，不想打了，放在这里。
「NOI2018」屠龙勇士 试一试这道题。爆炸了！多测又没有清空！一定要记住！多测一定要清空！清空！清空！希望不会再有类似的错误了，还有中间可能会爆 long long，要开 __int128。
中场休息
放一篇文章，是后天的内容，保存在这里，防止后天忘记。《小学生都能看懂的三类斯特林数从入门到升天教程》。
离散对数
大步小步算法，BSGS，拓展BSGS，还是很好理解的。就是相当于拆成根号进制（但是是减法），然后枚举。对于底数和模数不同余的情况就除以 gcd，还不同就继续。然后暴力就可以。
Luogu4195【模板】exBSGS/Spoj3105 Mod 直接上ex版本。
FFT/NTT
真神登场！回想了以前的写法，发现拓展性不是很好。于是决定以后都使用 vector 来实现，而且感觉这样会更好写，函数化实现。
这里放一下我的板子：
#include <bits/stdc++.h>
#define mod 998244353ll
using namespace std;
using ll = long long;
int n, m;
ll qp(ll x, ll y) {
ll ans = 1;
while (y) {
if (y & 1) ans = ans * x % mod;
y >>= 1;
x = x * x % mod;
}
return ans;
}
void ntt(vector<int>& a, int c, const vector<int>& rev, int lim) {
static ll inv3 = qp(3, mod - 2);
for (int i = 0; i < lim; ++i) if (i < rev[i]) swap(a[i], a[rev[i]]);
for (int i = 1; i < lim; i <<= 1) {
ll x = qp(~c ? 3 : inv3, (mod - 1) / (i << 1));
for (int j = 0; j < lim; j += (i << 1)) {
ll y = 1;
for (int k = 0; k < i; ++k, y = y * x % mod) {
ll p = a[j + k], q = a[j + k + i] * y % mod;
a[j + k] = (p + q) % mod;
a[j + k + i] = (p - q + mod) % mod;
}
}
}
if (c == -1) {
ll inv = qp(lim, mod - 2);
for (auto&& i : a) i = i * inv % mod;
}
}
vector<int> mult(vector<int> a, vector<int> b) {
int n = a.size(), m = b.size();
int lim, l = 0;
for (lim = 1; lim < n + m; lim <<= 1) ++l;
a.resize(lim), b.resize(lim);
vector<int> rev(lim);
for (int i = 0; i < lim; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));
ntt(a, 1, rev, lim), ntt(b, 1, rev, lim);
for (int i = 0; i < lim; ++i) a[i] = 1ll * a[i] * b[i] % mod;
ntt(a, -1, rev, lim);
a.resize(n + m - 1); //这一步很重要，在下面那道题中不加这个会 TLE！
return a;
}
int main() {
scanf("%d%d", &n, &m);
vector<int> a(n + 1), b(m + 1);
for (int i = 0; i <= n; ++i) {
scanf("%d", &a[i]);
}
for (int j = 0; j <= m; ++j) {
scanf("%d", &b[j]);
}
auto ans = mult(a, b);
for (int i = 0; i <= (n + m); ++i) {
printf("%d ", ans[i]);
}
return 0;
}
上周 Atcoder abc331_g 题刚好就是多项式，就写一下吧！就是先用 MIN-MAX 容斥一下，然后写一个式子画一下发现是几个多项式乘起来，直接放队列里面取前两个乘起来放进去就行，很方便。
记一下笔记：FWT(快速沃尔什变换)零基础详解qaq（ACM/OI）。
然后还复习了多项式求逆，现在也会推了，发现用 vector 真的写起来很帅！太可爱啦！
但是多项式还有好多东西啊……还有对数，exp，快速幂，下降幂多项式，多点求值，多项式复合逆，多项式开根……任重道远乎。
P.S. 话说真的有人把洛谷上多项式模板写完了的吗……
后记
今天太兴奋拉！今天的题目都好酷！哇酷哇酷哇酷！
眼中若空意何生，不怨不急道自得。
心向苍穹看虚妄，数在人心理可通。