多项式例题

发表于 2021-12-02 更新于 2022-02-10 分类于 OI 阅读次数：本文字数： 6.5k 阅读时长 ≈ 13 分钟

一些多项式以及生成函数的题目

Luogu P4389 付公主的背包

Link

Description

有 $n$ 种物品，每种物品体积为 $v$ ，每种商品有无数个，求凑出体积为 $m$ 的方案数。

$1\le n,m \le 10^5,1\le v_i \le m$

Solution

需要一些生成函数的知识。

对于每个物品我们知道他的生成函数长这样

F(x)=\sum_{i=0}^{\infty}x^{v\times i}=\frac{1}{1-x^v}

就是在 $v$ 的倍数处为 $1$ ，其余为 $0$ 。封闭形式只需要向右移动 $v$ 位，也就是乘 $x^v$ 。

暴力来做就把这 $n$ 个生成函数卷起来就行了。

\prod_{i=1}^n F(x)

考虑优化。在麦克劳林级数定义下的 $\ln$ 可以进行正常运算，我们可以把卷积这种复杂度较高的式子优化为加法。

\ln\ (\prod_{i=1}^n F(x) )=\sum_{i=1}^n\ln(F(x))

设 $G(x)=\ln(F(x))$

大力推式子

\begin{aligned} G'(x)&=\ln'(F(x))\\ &=\frac{F'(x)}{F(x)}\\ &=F'(x)(1-x^v)\\ &=\sum_{i=0}^{\infty}vix^{vi-1}(1-x^v)\\ &=\sum_{i=0}^{\infty}vix^{vi-1}-\sum_{i=0}^{\infty}vx^{v(i+1)-1}\\ &=\sum_{i=1}^{\infty}vix^{vi-1}-\sum_{i=1}^{\infty}v(i-1)x^{vi-1}\\ &=\sum_{i=1}^{\infty}vx^{vi-1}\\ G(x)=&\int G'(x)dx=\sum_{i=1}^{\infty}\frac{x^{vi}}{i} \end{aligned}

答案即为

\prod_{i=1}^n F(x)=\prod_{i=1}^n e^{G(x)} = e^{\sum_{i=1}^nG(x)}

我们只需要多项式的前 $m$ 项， $O(m)$ 求 $\sum_{i=1}^n G(x)$ ， $O(m\log m)$ 求多项式 exp，总复杂度 $O(m\log m)$ 。

Code

int n, m, tab[N];
ll inv[N], f[N << 2], g[N << 2];

int main()
{
    read(n), read(m);
    for(int i = 1, v; i <= n; i++)
        read(v), tab[v]++;

    inv[1] = 1;
    for(int i = 2; i <= m; i++)
        inv[i] = (p - p / i) * inv[p % i] % p;

    for(int i = 1; i <= m; i++)
    {
        if(!tab[i]) continue;
        ll tmp = i * tab[i] % p;
        for(int j = i; j <= m; j += i)
            g[j] = add(g[j] + tmp);
    }
    for(int i = 0; i <= m; i++)
        g[i] = g[i] * inv[i] % p;

    Exp(g, f, m + 1);

    for(int i = 1; i <= m; i++)
        write(f[i]), pc('\n');

    return 0;
}
// A.S.

Luogu P4841 [集训队作业2013]城市规划

Link

Description

求 $n$ 个点的的简单 (无重边无自环) 有标号无向连通图个数。

$n\le 130000$

Solution

设 $f(n)$ 表示 $n$ 个点的的简单有标号无向连通图个数， $g(n)$ 表示 $n$ 个点的有标号无向图个数。

显然 $g(n)=2^{\binom{n}{2}}$ ，因为共有 $\binom{n}{2}$ 条边，每条边都可以选或不选。

g(n)=\sum_{i=1}^n\binom{n-1}{i-1}f(i)g(n-i)

可以理解成枚举 $1$ 所在的连通块有几个点。

2^{\binom{n}{2}}=\sum_{i=1}^n\binom{n-1}{i-1}f(i)g(n-i) \\ 2^{\binom{n}{2}}=\sum_{i=1}^n\binom{n-1}{i-1}f(i)2^{\binom{n-i}{2}} \\ \dfrac{2^{\binom{n}{2}}}{(n-1)!}=\sum_{i=1}^n\dfrac{f(i)2^{\binom{n-i}{2}}}{(i-1)!(n-i)!}

然后我们其实已经有卷积的形式了。

设

F(x)=\sum_{n=1}^\infin\dfrac{f(n)}{(n-1)!} \\ G(x)=\sum_{n=1}^\infin\dfrac{2^{\binom{n}{2}}}{n!} \\ H(x)=\sum_{n=1}^\infin\dfrac{2^{\binom{n}{2}}}{(n-1)!}

那么

H(x)=F(x)*G(x) \\ F(x)=\dfrac{H(x)}{G(x)}

最后的答案即为 $F(x)$ 中 $x^n$ 的系数乘 $(n-1)!$

Code

int n;
ll fac[N];
ll f[N << 2], g[N << 2], gi[N << 2];

int main()
{
    read(n), n++;

    fac[0] = 1, g[0] = 1;
    for(int i = 1; i < n; i++) fac[i] = fac[i - 1] * i % p;
    for(int i = 1; i < n; i++) f[i] = qpow(2, 1ll * i * ( i - 1 ) / 2 % (p - 1)) * qpow(fac[i - 1], p - 2) % p;
    for(int i = 1; i < n; i++) g[i] = f[i] * qpow(i, p - 2) % p;

    Inv(g, gi, n);
    Mul(f, gi, n, n);

    write(f[n - 1] * fac[n - 2] % p), pc('\n');
    return 0;
}
// A.S.

Luogu P4723 【模板】常系数齐次线性递推

Link

Description

求一个满足 $k$ 阶齐次线性递推数列 ${a_i}$ 的第 $n$ 项，即：

a_n=\sum\limits_{i=1}^{k}f_i \times a_{n-i}

对 $998244353$ 取模

$n=10^9,k=32000$

Solution

懒得写了，直接放一下连接吧（，讲的太好了

题解 P4723 【模板】常系数齐次线性递推

但是题解区代码没一个能看的（

主要是注意一下边界，在乘法后项数会多一倍，所以取模时传的数组长度要为 $2m$ 。

不知道为啥常数非常大，不开 O2 一个点都过不去，可能是人傻常数大吧 qaq

Code

int n, m;
ll p[N], f[N], pr[N], pi[N];    //p: f, pr: rev(p), pi: inv(pr), f: a
ll a[N], b[N];

void Mod(ll *a, ll *b, int n, int m)
{
    int lim = calclim(n << 1);
    Copy(a, b, n), Clear(b, n, lim), reverse(b, b + n);
    Mul(b, pi, n, n - m + 2), Clear(b, n - m + 1, n + n - m + 2), reverse(b, b + n - m + 1);
    Mul(b, p, n - m + 2, m);
    for(int i = 0; i < m - 1; i++) b[i] = sub(a[i] - b[i]);
    return;
}

ll r[N];

void MulMod(ll *a, ll *b, int n, int m)
{
    int lim = calclim(n << 1);
    Clear(r, 0, lim);
    Mul(a, b, n, m);
    Mod(a, r, n + m, m);
    Copy(r, a, m - 1), Clear(a, m - 1, lim);
    return;
}

void Qpow(ll *a, ll *b, int k)
{
    b[0] = 1;
    while(k)
    {
        if(k & 1) MulMod(b, a, m, m);
        MulMod(a, a, m, m), k >>= 1;
    }
    return;
}

int main()
{
    read(n), read(m);
    for(int i = 1; i <= m; i++) read(pr[i]), pr[i] = sub(mod - pr[i] % mod), p[m - i] = pr[i];
    for(int i = 0; i < m; i++) read(f[i]);
    p[m] = pr[0] = 1, m++;
    Inv(pr, pi, m + 2);

    a[1] = 1;
    Qpow(a, b, n);

    ll ans = 0;
    for(int i = 0; i < m; i++)
        ans = (ans + f[i] * b[i] % mod + mod) % mod;
    write(ans), pc('\n');

    return 0;
}
// A.S.

CF438E The Child and Binary Tree

Link

Description

太长不想写（

Solution

设 $f_i$ 表示权值为 $i$ 的神犇二叉树的个数，即为所求， $g_i$ 表示有没有权值为 $i$ 的点。

g_i=0/1\\ f_n=1\ (n=0) \\ f_n=\sum_{i=1}^ng_i\sum_{j=i}^{n-i}f_{j}f_{n-i-j}\ (n>0) \\

可以发现这是三个多项式卷在一起

设 $F$ 表示 $f$ 的生成函数， $G$ 表示 $g$ 的生成函数

F=G*F^2+1

这里 $+1$ 是因为 $f_0=1$ 。

根据求根公式

F=\dfrac{1\pm \sqrt{1-4G}}{2G}

分类讨论一下 $\pm$ ，发现只能是 $-$ ，如果发现不了就都试一试就行了（

F=\dfrac{1-\sqrt{1-4G}}{2G}

分子分母同时 $\times (1+\sqrt{1-4G})$ ，得

F=\dfrac{2}{1+\sqrt{1-4G}}

这波分子无理化也属实 nb，因为 $2G$ 的常数项为 $0$ ，并不能求逆，而后面的式子有个 $+1$ 。

然后就是多项式求逆和多项式开根板子了

Code

int n, m;
ll f[N << 2], g[N << 2], sg[N << 2];

int main()
{
    read(n), read(m), m++;
    for(int i = 1, c; i <= n; i++)
        read(c), g[c] = 1;

    g[0] = 1;
    for(int i = 1; i < m; i++)
        g[i] = p - 4 * g[i] % p;

    Sqrt(g, sg, m);
    sg[0]++;
    Inv(sg, f, m);
    for(int i = 0; i < m; i++) f[i] = f[i] * 2 % p;

    for(int i = 1; i < m; i++) write(f[i]), pc('\n');
    pc('\n');

    return 0;
}
// A.S.

CF528D Fuzzy Search

Link

Description

给定两个只含 AGCT 的基因串 $S$ 和 $T$ ，求在下列规则中 $T$ 在 $S$ 中出现了几次。

$T$ 在 $S$ 的第 $i$ 个位置中出现，当且仅当把 $T$ 的首字符和 $S$ 的第 $i$ 个字符对齐后， $T$ 中的每一个字符能够在 $S$ 中找到一个位置偏差不超过 $k$ 的相同字符。

$1\le n\le m \le 2\times 10^5,0\le k \le 2\times 10^5$

Solution

因为只有四种字符，我们不妨对每个字符分别考虑，如果四种字符都合法，那么这个位置就是合法的。

对于偏差不超过 $k$ ，并不太好处理，但是我们只对一个字符考虑，所以可以将可以为该字符的位置赋成 $1$ ，其余的都赋成 $0$ ，即把在偏差 $k$ 以内的都改成该字符。

然后我们将得到的新的 $S$ 和 $T$ 分别设为 $f$ 和 $g$ ，都是 $01$ 串。

h_i=\sum_{j=0}^{m-1}g_j(f_{i+j}-g_j)^2

如果 $h_i=0$ ，就说明可以匹配。

平方是为了不会出现 $1+(-1)=0$ 的情况

\begin{aligned} h_i&=\sum_{j=0}^{m-1}g_j(f_{i+j}-g_j)^2 \\ &=\sum_{j=0}^{m-1}g_jf_{i+j}^2-g_j^3-2g_j^2f_{i+j} \\ &=\sum_{j=0}^{m-1}g_j-g_jf_{i+j} \end{aligned}

这里是因为 $f,g$ 都为 $01$ 串，所以三次方和平方都可以改为一次。

然后就套路地将 $g$ 翻转，就可以卷积了

h_i=\sum_{j=0}^{m-1}g_{m-1-j}-g_{m-1-j}f_{i+j}

Code

int n, m, k, lim;
char s[N], t[N];
ll f[N << 2], g[N << 2], h[N << 2];
int len[N];

void solve(char c)
{
    memset(f, 0, sizeof(f));
    memset(g, 0, sizeof(g));
    memset(h, 0, sizeof(h));

    for(int i = 0; i < n; i++)
        if(s[i] == c) f[i - k < 0 ? 0 : i - k]++, f[i + k + 1]--;
    for(int i = 0; i < n; i++) f[i] += f[i - 1];
    for(int i = 0; i < n; i++) if(f[i]) f[i] = 1;

    for(int i = 0; i < m; i++) g[i] = t[m - i - 1] == c;
    
    Mul(f, g, n, m);

    for(int i = 0; i < n; i++) len[i] += f[i];
    return;
}

int main()
{
    read(n), read(m), read(k);
    scanf("%s%s", s, t);

    solve('A'), solve('C'), solve('G'), solve('T');

    int ans = 0;
    for(int i = 0; i < n; i++)
        ans += (len[i] == m);
    write(ans), pc('\n');

    return 0;
}
// A.S.

Luogu P4173 残缺的字符串

Link

Description

给定一个长度为 $n$ 的字符串 $A$ 和一个长度为 $m$ 的字符串 $B$ ，仅由小写字母和 * 组成，其中 * 表示相应位置已经残缺，即可以为任意字母。

求对于 $B$ 的每一个位置 $i$ ，从这个位置开始连续 $n$ 个字符形成的子串是否可能与 $A$ 匹配。

$1\le n\le m \le 3\times 10^5$

Solution

经典通配符匹配问题

将 * 的位置赋成 0。

设 $A$ 和 $B$ 的差异为

d(A,B)=\sum_{i=0}^{n-1}(A_i-B_i)^2A_iB_i

那么 $B$ 以 $i$ 结尾的子串与 $A$ 完全匹配的条件为

f(i)=d(A,B[i-m+1,i])=0

比较套路地翻转 $A$ ，并写成卷积的形式

\begin{aligned} f(i)&=\sum_{j=0}^{i}(A_{i-j}-B_j)^2A_{i-j}B_j \\ &=\sum_{j=0}^iA_{i-j}^3B_j-A_{i-j}^2B_j^2+A_{i-j}B_j^3 \end{aligned}

然后就是三个卷积了，这里写的 FFT

Code

int n, m;
char S[N], T[N];
int s[N], t[N];
Complex a[N << 2], b[N << 2], c[N << 2];

int main()
{
    read(n), read(m);
    scanf("%s%s", S, T);
    for(int i = 0; i < n; i++) if(S[i] != '*') s[i] = S[i] - 'a' + 1;
    for(int i = 0; i < m; i++) if(T[i] != '*') t[i] = T[i] - 'a' + 1;
    reverse(s, s + n);

    int lim = calclim(n + m);
    calcrev(lim);

    for(int i = 0; i < lim; i++) a[i] = b[i] = Complex(0.0, 0.0);
    for(int i = 0; i < n; i++) a[i] = Complex(s[i] * s[i] * s[i], 0);
    for(int i = 0; i < m; i++) b[i] = Complex(t[i], 0);
    FFT(a, lim, 1), FFT(b, lim, 1);
    for(int i = 0; i < lim; i++) c[i] = a[i] * b[i];

    for(int i = 0; i < lim; i++) a[i] = b[i] = Complex(0.0, 0.0);
    for(int i = 0; i < n; i++) a[i] = Complex(s[i] * s[i], 0);
    for(int i = 0; i < m; i++) b[i] = Complex(t[i] * t[i], 0);
    FFT(a, lim, 1), FFT(b, lim, 1);
    for(int i = 0; i < lim; i++) c[i] = c[i] - a[i] * b[i] * 2.0;

    for(int i = 0; i < lim; i++) a[i] = b[i] = Complex(0.0, 0.0);
    for(int i = 0; i < n; i++) a[i] = Complex(s[i], 0);
    for(int i = 0; i < m; i++) b[i] = Complex(t[i] * t[i] * t[i], 0);
    FFT(a, lim, 1), FFT(b, lim, 1);
    for(int i = 0; i < lim; i++) c[i] = c[i] + a[i] * b[i];
    FFT(c, lim, -1);

    int ans = 0;
    for(int i = n - 1; i < m; i++)
        if(fabs(c[i].x) < 0.5) ans++;
    write(ans), pc('\n');
    for(int i = n - 1; i < m; i++)
        if(fabs(c[i].x) < 0.5) write(i - n + 2), pc(' ');
    pc('\n');

    return 0;
}

Luogu P3723 [AH2017/HNOI2017]礼物

Link

Description

给定两个长度为 $n$ 的数组 $a$ 和 $b$ ，求 $\sum_{i=1}^n(a_i+x-b_i)^2$ 的最小值。

$1\le n \le 50000,1\le a_i \le m \le 100$

Solution

将式子展开

\begin{aligned} &\sum_{i=1}^n(a_i+x-b_i)^2 \\ =&\sum_{i=1}^n(a_i^2+b_i^2+x^2+2a_ix-2a_ib_i-2bi_x) \\ =&\sum_{i=1}^na_i^2+\sum_{i=1}^nb_i^2+\sum_{i=1}^nx^2+2x\sum_{i=1}^n(a_i-b_i)-2\sum_{i=1}^na_ib_i \end{aligned}

一二项是定值，三四项就是个二次函数，只需要找到对称轴，然后找到两边最近的两个整数，算一下最小值即可。

x=\dfrac{\sum(b_i-a_i)}{n}

现在只需要将第五项最大化

也是套路地翻转一下 $b$ 数组，然后就可以卷积了，要将 $a$ 数组复制一倍，卷积后求 $x^n$ 到 $x^{2n-1}$ 的系数的最大值。

Code

int n, m;
ll a[N], b[N], sa, sb, ans;

ll calc(int x)
{
    return n * x * x + 2 * x * (sa - sb);
}

int main()
{
    read(n), read(m);
    for(int i = 0; i < n; i++) read(a[i]), a[i + n] = a[i], sa += a[i], ans += a[i] * a[i];
    for(int i = 0; i < n; i++) read(b[i]), sb += b[i], ans += b[i] * b[i];

    int x1 = floor(1.0 * (sb - sa) / n), x2 = ceil(1.0 * (sb - sa) / n);
    ans += min(calc(x1), calc(x2));

    reverse(b, b + n);
    Mul(a, b, n + n, n);

    ll mx = -1e18;
    for(int i = n; i < n * 2; i++) mx = max(mx, a[i]);
    ans -= (mx << 1);
    write(ans), pc('\n');
    return 0;
}
// A.S.