Submission #35956221

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int MOD = 998244353;

struct mint {
    int n;
    mint() : n(0) { ; }
    mint(ll m) {
        if (m < 0 || MOD <= m) {
            m %= MOD;

            if (m < 0)
                m += MOD;
        }

        n = m;
    }
    operator int() {
        return n;
    }
};
bool operator==(mint a, mint b) {
    return a.n == b.n;
}
mint operator+=(mint &a, mint b) {
    a.n += b.n;

    if (a.n >= MOD)
        a.n -= MOD;

    return a;
}
mint operator-=(mint &a, mint b) {
    a.n -= b.n;

    if (a.n < 0)
        a.n += MOD;

    return a;
}
mint operator*=(mint &a, mint b) {
    a.n = ((ll)a.n * b.n) % MOD;
    return a;
}
mint operator+(mint a, mint b) {
    return a += b;
}
mint operator-(mint a, mint b) {
    return a -= b;
}
mint operator*(mint a, mint b) {
    return a *= b;
}
template<typename T>
mint operator^(mint a, T n) {
    if (n == 0)
        return mint(1);

    mint res = (a * a) ^ (n / 2);

    if (n % 2)
        res = res * a;

    return res;
}
ll inv(ll a, ll p) {
    return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p);
}
mint operator/(mint a, mint b) {
    return a * mint(inv(b, MOD));
}
mint operator/=(mint &a, mint b) {
    a = a / b;
    return a;
}

vector<mint> fac, ifac;

void init(int n) {
    fac.resize(n + 1);
    ifac.resize(n + 1);
    fac[0] = ifac[0] = 1;

    for (int i = 1; i <= n; ++i)
        fac[i] = fac[i - 1] * mint(i);

    ifac[n] = mint(1) / fac[n];

    for (int i = n - 1; i >= 1; --i)
        ifac[i] = ifac[i + 1] * mint(i + 1);
}

mint C(int n, int m) {
    if (n < m || m < 0)
        return 0;

    assert(max(n, m) < fac.size());

    return fac[n] * ifac[m] * ifac[n - m];
}

mint A(int n, int m) {
    return fac[n] * ifac[n - m];
}

int main() {
    cin.tie(NULL)->ios_base::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<int> cnt(m), num(n + 1);

    init(n);

    for (int i = 1; i <= n; ++i) {
        ++cnt[i % m];
    }

    int mx = 0;

    for (int i = 0; i < m; ++i) {
        ++num[cnt[i]];

        if (cnt[i])
            mx = max(mx, cnt[i]);
    }

    auto ans = vector(n + 1, mint(0));

    for (int k = mx; k <= n; ++k) {
        mint res = 1;

        for (int j = 0; j <= n; ++j) {
            if (num[j]) {
                res *= A(k, j) ^ num[j];
            }
        }

        mint now = 1;

        for (int j = 0; j < k; ++j) {
            res -= ans[j] * now;
            now *= (k - j);
            //res -= ans[j] * A(k, k) / A(k - j, k - j);
        }

        res /= A(k, k);
        ans[k] = res;
    }

    for (int i = 1; i <= n; ++i)
        cout << ans[i] << "\n";

    return 0;
}

Submission Info

Compile Error

In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from ./Main.cpp:1:
./Main.cpp: In function ‘mint C(int, int)’:
./Main.cpp:101:22: warning: comparison of integer expressions of different signedness: ‘const int’ and ‘std::vector<mint>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  101 |     assert(max(n, m) < fac.size());
      |            ~~~~~~~~~~^~~~~~~~~~~~

Judge Result