Luogu P5087 数学

题意

给定一个长度为 \(n\) 的序列 \(a_i\)，求出在这个序列中所有选出 \(k\) 个元素方案中元素的乘积之和。

\(\texttt{Data Range:}1\leq n\leq 10^5,1\leq k\leq 300\)

题解

多项式乘法。

很明显答案为

\[[x^k]\prod\limits_{i=1}^{n}(1+a_ix)
\]

来考虑一下证明。

这些多项式乘积中 \(x^k\) 的系数相当于在 \(n\) 个多项式任意选出 \(k\) 个多项式，其中被选出来的的取一次项，剩下的取常数项，将这些东西乘起来的和。这个东西很明显是跟题目等价的。

同时注意到每个多项式是一次多项式所以可以 \(O(n)\) 乘起来，总复杂度 \(O(nk)\)。

考虑一个加强版，其中 \(1\leq n\leq 5\times 10^5,1\leq k\leq 5\times10^5\) 并且对 \(998244353\) 取模，这个时候剩下题解中的 DP 就基本上不能用了，而如果以多项式乘法的角度去思考的话发现这个东西可以分治 NTT，然后 \(O(n\log^2n)\) 就做完了。

代码

#include<bits/stdc++.h>

using namespace std;

typedef int ll;

typedef long long int li;

const ll MAXN=2e5+51,MOD=1e9+7;

ll n,kk,c,x;

ll f[MAXN];

inline ll read()

{

    register ll num=0,neg=1;

    register char ch=getchar();

    while(!isdigit(ch)&&ch!='-')

    {

        ch=getchar();

    }

    if(ch=='-')

    {

        neg=-1;

        ch=getchar();

    }

    while(isdigit(ch))

    {

        num=(num<<3)+(num<<1)+(ch-'0');

        ch=getchar();

    }

    return num*neg;

}

int main()

{

    n=read(),kk=read(),f[0]=1;

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

    {

        x=read();

        for(register int j=c;j>=0;j--)

        {

            f[j+1]=(f[j+1]+(li)f[j]*x%MOD)%MOD;

        }

        c=c==kk?kk:c+1;

    }

    printf("%d\n",f[kk]);

}

巴特西

Luogu P5087 数学

题意

题解

代码

最新文章

热门文章