题解：AT_abc436_g [ABC436G] Linear Inequation
cheng2010
·
·
题解
简单题。
考虑直接列出生成函数。
先对每个数字列出生成函数，即 <1,a_i,2a_i,3a_i,\dots>，等于 \frac{1}{1-x^a_i}。
那么记 F(x)=\prod (\dfrac{1}{1-x^{a_i}})，答案就是 \sum_{i=0}^{m} [x^i]F(x)。
但是 m 很大，考虑优化。
考虑前缀和的意义，就是 F(x) 与全是 1 的多项式的卷积，那么可化成 [x^k]\frac{1}{(1-x)F(x)}，发现是喜闻乐见的 BM 的形式，做完了。
:::info[不熟悉 BM 的看这里]
考虑这样一个问题：求 [x^k]\frac{g(x)}{f(x)}。
先同时乘一个 f(-x)，变成 [x^k]\frac{g(x)f(-x)}{f(x)f(-x)}，考虑 f(x)f(-x) 奇数项全是 0，可写作 H(x^2)。
然后令 g(x)f(-x)=F(x^2)+xG(x^2)。
原式变成 [x^k](\frac{F(x^2)}{H(x^2)}+\frac{xG(x^2)}{H(x^2)})，前面的只会贡献偶数向，后面的为奇数项，然后由于自变量是 x^2，可除去 2，故结论为：
[x^k]\frac{g(x)}{f(x)}=
\begin{cases}
[x^{ \frac{k}{2}}]\frac{F(x)}{H(x)} & 2 \mid k\\
\\
[x^{ \frac{k-1}{2}}]\frac{G(x)}{H(x)} & 2\nmid k\\
\end{cases}
:::
代码是好写的。
:::success[code]
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=(1<<20)+1;
mt19937 rnd(time(0));
const int Mod=998244353;
inline int mul(int a,int b)
{
unsigned long long res=1ull*a*b;
return res>Mod?res%Mod:res;
}
inline int add(int a,int b)
{
a+=b;return a>Mod?a-Mod:a;
}
inline int ks(int a,int b)
{
int res=1;
while(b)
{
if(b&1) res=mul(res,a);
a=mul(a,a);
b>>=1;
}
return res;
}
namespace Poly
{
/*
多项式板子
*/
inline int BM(int *f,int n,int *g,int m,ll k)
{
for(int i=0;i<=n;i++) ar[i]=f[i];
for(int i=0;i<=m;i++) br[i]=g[i];
for(;k;k>>=1)
{
for(int i=0;i<=m;i++)fz[i]=br[i];
for(int i=1;i<=m;i+=2)fz[i]=Mod-fz[i];
Poly::getmul(ar,n,fz,m,ar);
Poly::getmul(br,m,fz,m,br);
for(int i=0;i<=m;i++)fz[i]=0;
int j=0;
for(int i=(k&1);i<=n+m;i+=2,j++)ar[i/2]=ar[i];
for(int i=j;i<=n+m;i++)ar[i]=0;n=j-1,j=0;
for(int i=0;i<=2*m;i+=2,j++)br[i/2]=br[i];
for(int i=j;i<=2*m;i++)br[i]=0;m=j-1;
}
int a0=ar[0],b0=br[0];ar[0]=br[0]=0;
return mul(a0,ks(b0,Mod-2));
}
}
int n;
ll m;
int la;
int a[N],b[N];
signed main()
{
Poly::prework();
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;a[0]=1;
for(int i=0;i<=n;i++)
{
int x;
if(i==1) x=1;
else cin>>x;
for(int j=0;j<=la;j++) b[j+x]=Mod-a[j];la+=x;
for(int j=0;j<=la;j++) a[j]=add(a[j],b[j]);
for(int j=0;j<=la;j++) b[j]=0;
}
b[0]=1;
cout<<Poly::BM(b,0,a,la,m);
}
```
:::