Submission #69119838

---

Source Code Expand

#include <algorithm>
#include <iostream>
#include <vector>

#include <atcoder/all>

int main()
{
    using namespace std;
    int n, a, b, c;
    cin >> n >> a >> b >> c;
    using mint = atcoder::modint998244353;
    int nn = n + 1;

    vector<mint> fact(nn, 1), invfact(nn, 1);
    for (int i = 0; i < nn - 1; i++) fact[i + 1] = fact[i] * (i + 1);
    invfact[nn - 1] = fact[nn - 1].inv();
    for (int i = nn - 2; i >= 0; i--) invfact[i] = invfact[i + 1] * (i + 1);


    auto solve1 = [&] {
        vector<mint> f(n + 1);
        f[0] = 1;
        for (int p : {a, b, c}) {
            for (int i = 0; i < nn - p; ++i) {
                f[i + p] += f[i];
            }
        }
        return f[n];
    };
    cout << solve1().val() << "\n";
    auto solve2 = [&] {
        vector<mint> f(n + 1);
        f[0] = fact[n];
        for (int p : {a, b, c}) {
            vector<mint> fp(n + 1);
            for (int i = 0; i < nn; i += p) {
                fp[i] = invfact[i];
            }
            auto g = atcoder::convolution(f, fp);
            f = vector(g.begin(), g.begin() + nn);
        }
        return f[n];
    };
    cout << solve2().val() << "\n";
}

Submission Info

Judge Result