多项式基础知识（3）

例题（本部分主要讲解一些比较经典的多项式问题和一些$icpc$区域赛的真题）

付公主的背包（洛谷P4389）

付公主有一个可爱的背包qwq,这个背包最多可以装 $10^5$ 大小的东西
付公主有 $n$ 种商品，她要准备出摊了，每种商品体积为 $v_i$，都有无限件.给定 $m$，对于 $s\in [1,m]$，请你回答用这些商品恰好装 $s$ 体积的方案数.
第一行两个正整数 $n,m$。
第二行 $n$ 个正整数，表示每种商品的体积。
$1\le n,m \le 10^5$，$1\le v_i \le m$。

此题为一道经典题目，利用生成函数优化完全背包问题.

完全背包问题的朴素做法为设$dp[i][j]$为用前$i$种物品恰好装满体积$j$的方案数，但时间复杂度为$O(nm)$，不能通过此题.

接下来考虑如何进行优化，我们对一个体积为$V$的物品构建生成函数：

$S(x)=\sum_{i=0}^{\infty}x^{iV}=\frac{1}{1-x^V}$

答案则为$m$个生成函数相乘后的$[x^s]$，但直接做的时间复杂度为$O(nmlogn)$，仍然不能通过此题.

考虑如何对该式子进行变形，想到把式子两边取对数，这样可以把乘法转换成加法

$\ln{A(x)}=-\ln{(1-x^V)}$

对$\ln{(1-x^V)}$进行泰勒展开得：

$\ln{A(x)}=\sum_{i\geq1}\frac{x^{iv}}i$

最后做完加法后，再做一下$exp$还原回去即可.

注意：代码中调用的封装函数均为上篇文章的多项式模板.

int b[N];
int inv[N];

void solve(){
    int n , m;
    cin >> n >> m;
    poly a;
    int lim = 1;
    for(;lim <= m ; lim *= 2);
    // for(int i = 0 ; i <= lim ; i ++)a[i] = 0;
    init_poly(m);
    // init_inv(lim + 1);
    for(int i = 1 ; i <= n ; i ++){
        int x;
        cin >> x;
        b[x] ++;
    }
    inv[0]=inv[1]=1;
    for(int i=2;i<N;++i)inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;
    for(int i = 1 ; i <= m ; i ++){
        if(b[i] == 0)continue;
        for(int j = i ; j < lim ; j += i)
            a[j] = ((LL)a[j] + (LL)b[i] * (mod - inv[j / i]) % mod) % mod;
    }
    // for(int i = 1 ; i <= m ; i ++)cout << a[i] << ' ';
    // cout << endl;
    // a.resize(m);
    // a.exp().print(m);
    poly c = a.exp().inv();
    for(int i = 1 ; i <= m ; i ++)cout << c[i] << '\n';
    cout << endl;
}

signed main(){
    // freopen("test.in","r",stdin);
    // freopen("test.out","w",stdout);
    int T = 1;
    // cin >> T;
    while(T --){
        solve();
    }
    return 0;
}

[THUPC 2017] 小 L 的计算题

现有一个长度为 $n$ 的非负整数数组 $\{a_i\}$ 。小 L 定义了一种神奇变换：

$f_k=\left(\sum_{i=1}^na_i^k\right)\bmod 998244353$

小 L 计划用变换生成的序列 $f$ 做一些有趣的事情，但是他并不擅长算乘法，所以来找你帮忙，希望你能帮他尽快计算出 $f_{1\dots n}$。

输入格式

输入包含多组数据。
输入的第一行包含一个整数 $T$ , 表示数据组数。接下来 $2T$ 行，每两行代表一组测试数据。每组数据的第一行包含一个整数 $n$，表示数组 $\{a_i\}$ 的长度。接下来一行 $n$ 个整数，描述数组 $\{a_i\}$。
保证输入的 $a_i$ 满足 $0\le a_i\le10^9$。在一个测试文件中，保证有 $\sum n\le 4\times 10^5$。

输出格式

我们不想让你输出过多的数。因此，令 $ans=\bigoplus_{i=1}^{n}f_i$，其中 $\bigoplus$ 表示异或操作，在 C++ / Java / Python 中，它可以表示为 ^。对每组数据，你需要输出一行一个整数，表示 $ans$。

此题为比较模板的题，可以先构造生成函数$F(x)=\sum_{k\geq1}x^k\sum_{i=1}^na_i^k$.

（为什么要这样构造？是为了把$x^k$的系数刚好变为题目中要求的答案$f(k)$）.

接下来对该式子进行化简：

$\begin{aligned} F(x)&=\sum_{k\geq1}x^k\sum_{i=1}^na_i^k\\ &=\sum_{i=1}^n\sum_{k\geq1}(a_ix)^k\\ &=\sum_{i=1}^n\frac{xa_i}{1-xa_i}\\ &=\frac{\sum_{i=1}^na_i\prod_{j\neq i}(1-xa_j)}{\prod_{i=1}^n(1-xa_i)} \end{aligned}$

经过观察发现分子为分母的导数，而分母可以通过分治$NTT$在$O(nlog^2n)$时间复杂度解决.然后只需再利用多项式求逆和多项式乘法即可得到最后的$F(x)$.

int n;
LL c[N];

poly work(int l , int r){
    if(l == r){
        poly t;
        t[0] = 1 , t[1] = ((mod - c[l]) % mod + mod) % mod;
        return t;
    }
    int mid = (l + r) >> 1;
    return work(l , mid) * work(mid + 1 , r);
}

void solve(){
    cin >> n;
    for(int i = 1 ; i <= n ; i ++)cin >> c[i];
    
    poly a = work(1 , n);
    poly b = a.der();
    b = -b * a.inv();
    b.resize(n + 1);
    ull res = 0;
    for(int i = 0 ; i < n ; i ++)res ^= b[i];
    cout << res << endl;
}

signed main(){
    int T;
    cin >> T;
    init_poly(N / 2);
    while(T --){
        solve();
    }
    return 0;
}

[THUPC 2023 初赛] 快速 LCM 变换

小 I 今天学习了快速最小公倍数变换（Fast Least-Common-Multiple Transform, FLT），于是他想考考你。给定一个长度为 $n$ 的正整数序列 $r_1,r_2,\cdots,r_n$。你需要做以下操作恰好一次：
选择整数 $i,j$ 使得 $1 \le i < j \le n$。在序列末尾加入 $(r_i+r_j)$，并将 $r_i$ 和 $r_j$ 从序列中删除。
可以注意到总共有 $\frac{n(n-1)}{2}$ 种可能的操作，每种操作会得到一个长度为 $n-1$ 的序列。
你需要对所有的这 $\frac{n(n-1)}{2}$ 个序列，求出序列中所有元素的最小公倍数，并给出它们的和模 $998244353$ 的值。

输入格式

输入的第一行包含一个正整数 $n$，表示序列的长度。接下来一行 $n$ 个正整数 $r_1,r_2,\cdots,r_n$，描述初始序列。$2 \le n \le 5 \times 10^5, 1 \le r_1,r_2,\cdots,r_n \le 10^6$。

输出格式

输出一行一个整数，表示所有序列的最小公倍数的和模 $998244353$ 的值。

本题的难点在于通过利用数论的知识如何把题目中的条件转换为卷积的形式.

发现直接去算较为困难，我们考虑对于每个质数$p$对答案的贡献.设$r_i$有$k_1$个$p(k_1=v_p(r_i))$，$r_j$有$k_2$个$p$，$r_i+r_j$有$k_3$个$p$，且$p$在所有的$r$中最高次数为$mx_p$，次高次数(非严格)为$smx_p$，不妨设$k_1\geq k_2$.

当$k_1> k_2$时，若$k_1=mx_p$，则相加后$p$的最大次数变为$smx_p$，否则相加后$p$的最大次数不变.

当$k_1=k_2$时，相加后$p$的最大次数变为$max(k_3,mx_p)$.

计算$(i,j)$的贡献时，先考虑第一种情况：若$_p(r_i)=mx_p$,
则$lcm$乘上$\frac{1}{p^{mx_p-smx_p}}$.

然后加入第二种情况的贡献，若$v_p(r_i+r_j)>mx_p$，则$lcm$乘上$p^{v_p(r_i+r_j)-mx_p}$.

然后对于每个$k$，计算$r_i+r_j=k$的卷积即可.

const int MXN = 2e6;
const int S = 2.1e6 + 100;

int a[S] , n;
poly h;
int g[S] , md[S];
int fact[S] , infact[N];
int fmx[S] , smx[S];
int inv[S];
int f[S];

int qmi(int a , int b){
    int res = 1;
    while(b){
        if(b & 1)res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int init(){
    inv[0] = 1 , inv[1] = 1;
    for(int i = 1 ; i <= MXN ; i ++)inv[i] = qmi(i , mod - 2);
    md[1] = 1;
    for(int i = 2 ; i <= MXN ; i ++){
        if(md[i])continue;
        for(int j = i ; j <= MXN ; j += i){
            md[j] = i;
        }
    }
    for(int i = 1 ; i <= n ; i ++){
        int cur = a[i];
        while(cur > 1){
            int p = md[cur] , s = 1;
            while(md[cur] == p)s *= p , cur /= p;
            if(s > fmx[p])swap(fmx[p] , s);
            if(s > smx[p])swap(smx[p] , s);
        }
    }
    int lc = 1;
    for(int i = 1 ; i <= MXN ; i ++)if(fmx[i])lc = lc * fmx[i] % mod;
    for(int i = 1 ; i <= n ; i ++){
        int cur = a[i] , t = lc;
        while(cur > 1){
            int p = md[cur] , s = 1;
            while(p == md[cur])s *= p , cur /= p;
            if(s > smx[p])t = t * inv[s] % mod * max(1ll , smx[p]) % mod;
        }
        f[i] = t;
    }
    for(int i = 1 ; i <= MXN ; i ++){
        int cur = i , t = lc;
        while(cur > 1){
            int p = md[cur] , s = 1;
            while(p == md[cur])s *= p , cur /= p;
            if(s > fmx[p])t = t * inv[fmx[p]] % mod * s % mod;
        }
        g[i] = t;
    }
    return lc;
}

// const int M = 1e6;

signed main(){
    cin >> n;
    for(int i = 1 ; i <= n ; i ++)cin >> a[i];
    init_poly(MXN);
    int lc = init();
    for(int i = 1 ; i <= n ; i ++)h[a[i]] = (h[a[i]] + f[i]) % mod;
    h = h * h;
    int res = 0;
    for(int i = 1 ; i <= n ; i ++)h[a[i] + a[i]] = ((h[a[i] + a[i]] - f[i] * f[i] % mod) % mod + mod) % mod;
    for(int i = 1 ; i <= MXN ; i ++){
        res = (res + h[i] * g[i] % mod) % mod;
    }
    lc = lc * lc % mod;
    lc = qmi(lc , mod - 2);
    cout << res * lc % mod * inv[2] % mod << endl;
    return 0;
}