题解：AT_abc422_g [ABC422G] Balls and Boxes

· · 题解

第一问可以构造 OGF：

直接卷积，计算 $[x^n]F(x)$ 就行。 第二问由于有了顺序，所以考虑 EGF：$\hat{F}(x)=\left(1+\frac{x^a}{a!}+\frac{x^{2a}}{(2a)!}+\cdots\right)\left(1+\frac{x^b}{b!}+\frac{x^{2b}}{(2b)!}+\cdots\right)\left(1+\frac{x^c}{c!}+\frac{x^{2c}}{(2c)!}+\cdots\right)

仍然可以直接卷积，注意卷积的时候带上阶乘。最后计算 [x^n]\hat{F}(x) 时记得乘上 n! 即可。

注意到 \texttt{ACLibrary} 是一个好东西，因为 \texttt{Atcoder} 自带了卷积函数以及模数为 998244353 的 \texttt{Modint}。


#include<bits/stdc++.h>
#include<atcoder/all>
#define ll atcoder::modint998244353
using namespace std;
constexpr int N=3e5+5;int n,a,b,c;
vector<ll> f,g,h;ll fac[N];
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>a>>b>>c;
    f.resize(n+1);g.resize(n+1);h.resize(n+1);
    fac[0]=ll(1);
    for(int i=0;i<=n;i++){
        f[i]=(i%a==0);g[i]=(i%b==0);h[i]=(i%c==0);
        if(i!=0)fac[i]=fac[i-1]*(ll(i));
    }
    f=convolution(f,g);
    f=convolution(f,h);
    cout<<f[n].val()<<"\n";
    for(int i=0;i<=n;i++)f[i]=(i%a==0?fac[i].inv():0),g[i]=(i%b==0?fac[i].inv():0),h[i]=(i%c==0?fac[i].inv():0);
    f=convolution(f,g);f=convolution(f,h);
    cout<<((f[n]*fac[n]).val())<<"\n";
    return 0;
}