【Luogu4389】付公主的背包

题目

传送门

解法

答案显然是\(n\)个形如\(\sum_{i \geq 1} x^{vi}\)的多项式的卷积

然而直接NTT的时间复杂度是\(O(nm\log n)\)

我们可以把每个多项式求\(\ln\)然后相加，在\(\exp\)回去

我们设\(f(x) = \sum_{i \geq 1} x^{vi}\)， \(g(x) = \ln(f(x))\)

我们知道\(f(x) = \frac{1}{1-x^v}\)

于是

\[\begin{align}
g'(x) &= \frac{f'(x)}{f(x)}\\
&= \frac{f'(x)}{1/(1-x^v)}\\
&= (1-x^v)f'(x)\\
&= (1-x^v)\sum_{i \geq 1} v\times i\times x^{vi-1}\\
&= \sum_{i \geq 1} v\times i\times x^{vi-1} - \sum_{i \geq 1} v\times i\times x^{vi}\\
&= \sum_{i \geq 1} v\times \left[i - (i-1)\right]\times x^{vi-1}\\
&= \sum_{i \geq 1} v\times x^{vi-1}
\end{align}
\]

接着积分

\[g(x) = \int g'(x) \mathbb{d}x = \sum_{i \geq 1} \frac{1}{i}x^{vi}
\]

最后再跑多项式exp就行了

代码

// luogu-judger-enable-o2

#include <iostream>

#include <cstdlib>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 400010;

const LL mod = 998244353LL;

inline LL power(LL a, LL n, LL mod)

{	LL Ans = 1;

    while (n)

    {	if (n & 1) Ans = (Ans * a) % mod;

        a = (a * a) % mod;

        n >>= 1;

    }

    return Ans;

}

inline LL Plus(LL a, LL b) { return a + b > mod ? a + b - mod : a + b; }

inline LL Minus(LL a, LL b) { return a - b < 0 ? a - b + mod : a - b; }

struct Mul

{	int Len;

    int rev[N];

    LL wn[N];

    void getReverse()

    {	for (int i = 0; i < Len; i++)

            rev[i] = (rev[i>>1] >> 1) | ((i&1) * (Len >> 1));

    }

    void NTT(LL * a, int opt)

    {	getReverse();

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

            if (i < rev[i]) swap(a[i], a[rev[i]]);

        int cnt = 0;

        for (int i = 2; i <= Len; i <<= 1)

        {	cnt++;

            for (int j = 0; j < Len; j += i)

            {	LL w = 1;

                for (int k = 0; k < (i>>1); k++)

                {	LL x = a[j + k];

                    LL y = (w * a[j + k + (i>>1)]) % mod;

                    a[j + k] = Plus(x, y);

                    a[j + k + (i>>1)] = Minus(x, y);

                    w = (w * wn[cnt]) % mod;

                }

            }

        }

        if (opt == -1)

        {	reverse(a + 1, a + Len);

            LL num = power(Len, mod-2, mod);

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

                a[i] = (a[i] * num) % mod;

        }

    }

    void init()

    {	for (int i = 0; i < 23; i++)

            wn[i] = power(3LL, (mod-1) / (1 << i), mod);

    }

    void getLen(int l)

    {	Len = 1;

        for (; Len <= l; Len <<= 1);

    }

} Calc;

void cpy(LL * A, LL * B, int len1, int len2)

{	for (int i = 0; i < len1; i++) A[i] = B[i];

    for (int i = len1; i < len2; i++) A[i] = 0;

}

void getInv(LL * A, LL * B, int len)

{	static LL tmp1[N], tmp2[N];

    B[0] = power(A[0], mod-2, mod);

    for (register int i = 2; i <= len; i <<= 1)

    {	Calc.Len = i << 1;

        cpy(tmp1, A, i, Calc.Len);

        cpy(tmp2, B, i >> 1, Calc.Len);

        Calc.NTT(tmp1, 1);

        Calc.NTT(tmp2, 1);

        for (register int j = 0; j < Calc.Len; j++)

            tmp1[j] = Minus(Plus(tmp2[j], tmp2[j]), tmp2[j] * tmp2[j] % mod * tmp1[j] % mod);

        Calc.NTT(tmp1, -1);

        for (register int j = 0; j < i; j++)

            B[j] = tmp1[j];

    }

}

void getDeri(LL * a, int len)

{	for (int i = 0; i < len; i++)

        a[i] = a[i+1] * (LL) (i+1) % mod;

}

void getInte(LL * a, int len)

{	for (int i = len-1; i >= 1; i--)

        a[i] = a[i-1] * power(i, mod-2, mod) % mod;

    a[0] = 0;

}

void getLn(LL * A, int len)

{	static LL tmp1[N], tmp2[N], tmp3[N];

    Calc.Len = len << 1;

    cpy(tmp1, A, len, Calc.Len);

    cpy(tmp2, A, len, Calc.Len);

    getDeri(tmp1, len);

    getInv(tmp2, tmp3, len);

    Calc.Len = len << 1;

    Calc.NTT(tmp1, 1);

    Calc.NTT(tmp3, 1);

    for (int i = 0; i < Calc.Len; i++)

        tmp1[i] = tmp1[i] * tmp3[i] % mod;

    Calc.NTT(tmp1, -1);

    for (int i = len; i < Calc.Len; i++)

        tmp1[i] = 0;

    getInte(tmp1, len);

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

        A[i] = tmp1[i];

}

void getExp(LL * A, LL * B, int len)

{	static LL tmp1[N], tmp2[N];

    B[0] = 1;

    for (int i = 2; i <= len; i <<= 1)

    {	Calc.Len = i << 1;

        cpy(tmp1, B, i, Calc.Len);

        cpy(tmp2, B, i, Calc.Len);

        getLn(tmp1, i);

        Calc.Len = i << 1;

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

            tmp1[j] = Minus(A[j], tmp1[j]);

        tmp1[0]++;

        Calc.NTT(tmp1, 1);

        Calc.NTT(tmp2, 1);

        for (int j = 0; j < Calc.Len; j++)

            tmp1[j] = (tmp1[j] * tmp2[j]) % mod;

        Calc.NTT(tmp1, -1);

        for (int j = 0; j < Calc.Len; j++)

            B[j] = tmp1[j];

    }

}

LL A[N], B[N], Ans[N];

int cnt[N];

int v[N];

int main()

{	int n, m;

    scanf("%d %d", &n, &m);

    Calc.init();

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

    {	scanf("%d", &v[i]);

        cnt[v[i]]++;

    }

    Calc.init();

    Calc.getLen(m);

    int len = Calc.Len;

    for (int i = 1; i <= m; i++)

    {	if (!cnt[i]) continue;

        for (int j = i; j <= m; j += i)

            A[j] = Plus(A[j], (LL) cnt[i] * i % mod * power(j, mod-2, mod) % mod);

    }

    getExp(A, Ans, len);

    for (int i = 1; i <= m; i++)

        printf("%lld\n", Ans[i]);

    return 0;

}

巴特西

【Luogu4389】付公主的背包

题目

解法

代码

最新文章

热门文章