結果

問題 No.2130 分配方法の数え上げ mod 998244353
コンテスト
ユーザー Carpenters-Cat
提出日時 2022-11-25 21:49:09
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 17 ms / 2,000 ms
コード長 7,686 bytes
コンパイル時間 1,395 ms
コンパイル使用メモリ 129,824 KB
最終ジャッジ日時 2025-02-09 00:08:54
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <stdio.h>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

namespace
{
long long modinv(const long long& a, const long long& m)
{
    long long s = a;
    long long t = m;
    long long xs = 1;
    long long xt = 0;
    while (s) {
        long long q = t / s;
        t -= q * s;
        std::swap(s, t);
        xt -= q * s;
        std::swap(xs, xt);
    }
    assert(t == 1);
    while (xt < 0) {
        xt += m;
    }
    while (xt >= m) {
        xt -= m;
    }
    return xt;
}
}  // namespace

class mint
{
private:
    long long val;
    long long raw;

public:
    static long long mod;
    static long long mod_inv;
    mint(long long v = 0) : val(v), raw(v)
    {
        assert(mod > 1 && mod < (1ll << 31));
        if (val < 0) {
            val = (-val) % mod;
            val = mod - val;
            if (val == mod) {
                val = 0;
            }
        } else if (val >= mod) {
            val %= mod;
        }
    }
    explicit mint(long long v, long long r) : val(v), raw(r) {}
    mint operator=(const mint& m)
    {
        val = m.val;
        raw = m.raw;
        return *this;
    }
    long long gval() const
    {
        return this->val;
    }
    long long graw() const
    {
        return this->raw;
    }
    mint operator+(const mint& m) const
    {
        return mint{(val + m.val >= mod ? (val + m.val - mod) : (val + m.val)),
            raw + m.raw};
    }
    mint operator-(const mint& m) const
    {
        return mint{(val - m.val < 0 ? (val - m.val + mod) : (val - m.val)),
            raw - m.raw};
    }
    mint operator*(const mint& m) const
    {
        // とりあえず愚直計算。
        // 暇な時に高速なのにしておく
        return mint{(val * m.val) % mod, raw * m.raw};
    }
    mint inv() const
    {
        long long v2 = modinv(val, mod);
        return v2;
    }
    mint operator/(const mint& m) const
    {
        return (*this) * m.inv();
    }
    void operator+=(const mint& m)
    {
        *this = (*this) + m;
    }
    void operator-=(const mint& m)
    {
        *this = (*this) - m;
    }
    void operator*=(const mint& m)
    {
        *this = (*this) * m;
    }
    void operator/=(const mint& m)
    {
        *this = (*this) / m;
    }
};

void init(long long m)
{
    mint::mod = m;
    // mint::mod_inv = (-1ull) / m + 1;
}

std::ostream& operator<<(std::ostream& stream, const mint& m)
{
    const std::string sv = std::to_string(m.gval());
    stream << sv;
    return stream;
}

class big_mint
{
};
using ll = long long;
using Vi = vector<int>;
using VVi = vector<Vi>;
using Vl = vector<ll>;
using VVl = vector<Vl>;
using Pii = pair<int, int>;
using Vp = vector<Pii>;
using VVp = vector<Vp>;
using Pl = pair<ll, int>;
using Vpl = vector<Pl>;
using VVpl = vector<Vpl>;
using tup = tuple<ll, ll, int>;
using Vt = vector<tuple<int, int, int>>;
using Pll = pair<ll, ll>;
using Vc = vector<char>;
using VVc = vector<Vc>;
template <class U>
using PQmax = priority_queue<U>;
template <class U>
using PQmin = priority_queue<U, vector<U>, greater<U>>;


//再帰で計算するトポロジカルソート
void tprsort(int u, const VVi& gr, Vi& tpr, Vi& par);
//キューで計算するトポロジカルソート
void tprsort(const VVi& gr, Vi& tpr);
ll mpow(ll x, ll n, ll m = 1e9 + 7);
ll comb(int n, int r, const Vl& kai, const Vl& fkai, ll m = 1e9 + 7);
ll gcd(ll a, ll b);
int LCA(const VVi& par, const Vi& depth, int a, int b);
Vi sccResolve(const VVi& gr);
void dijkstra(const VVi& gr, const VVl& cost, Vl& dist, int s);

ll mint::mod = 998244353;

struct S {
    mint val;
    ll siz;
};
S comp(S a, S b)
{
    return S{a.val + b.val, a.siz + b.siz};
}
using F = mint;
S mapp(S a, F b)
{
    return S{a.val + b * a.siz, a.siz};
}
F fnc(F a, F b)
{
    return F{a + b};
}
S e{0, 1};
F id{0};

int main()
{
    ll N, M;
    cin >> N >> M;
    ll ans = 0;
    ll kj = 1;
    if (N < M) {
        cout << 0 << endl;
        return 0;
    }
    ll m = 998244353;
    ll n = N % m;
    for (int i = 0; i < M; i++) {
        ans += kj;
        ans %= m;
        kj *= (n - i);
        kj %= m;
        kj *= mpow(i + 1, m - 2, m);
        kj %= m;
    }
    ll sm = mpow(2, N, mint::mod);
    ans = sm - ans + m;
    ans %= m;
    cout << ans << endl;
}

// Library
void tprsort(int u, const VVi& gr, Vi& tpr, Vi& par)
{
    // idx[u] = tpr.size();
    /*for (int v : gr[u]) {
        if (par[v] == u || par[v] == -1) {
            par[v] = u;
            tprsort(v, gr, tpr, par);
        }
    }
    tpr.push_back(u);*/
    stack<int> st;
    st.push(u);
    bool vis[2000020];
    for (int i = 0; i <= gr.size(); i++) {
        vis[i] = false;
    }
    while (!st.empty()) {
        int v = st.top();
        if (!vis[v]) {
            vis[v] = true;
            for (int p : gr[v]) {
                if (par[p] == -1) {
                    par[p] = v;
                    st.push(p);
                }
            }
        } else {
            tpr.push_back(v);
            st.pop();
        }
    }
}

Vi sccResolve(const VVi& gr)
{
    int N = gr.size();
    Vi tpr;
    Vi par(N, -1);
    for (int i = 0; i < N; i++) {
        if (par[i] == -1) {
            tprsort(i, gr, tpr, par);
        }
    }
    Vi ret(N, -1);
    int now = 0;
    for (int i = N - 1; i >= 0; i--) {
        int u = tpr[i];
        if (ret[u] != -1) {
            continue;
        }
        ret[u] = now;
        stack<int> st;
        st.push(u);
        while (!st.empty()) {
            int v = st.top();
            st.pop();
            for (int p : gr[v]) {
                if (ret[p] == -1) {
                    st.push(p);
                    ret[p] = now;
                }
            }
        }
        now++;
    }
    return ret;
}

ll gcd(ll a, ll b)
{
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}
ll mpow(ll x, ll n, ll m)
{
    ll ret = 1;
    while (n) {
        if (n % 2) {
            ret *= x;
            ret %= m;
        }
        x = (x * x) % m;
        n /= 2;
    }
    return ret;
}
ll comb(int n, int r, const Vl& kai, const Vl& fkai, ll m)
{
    if (n < 0 || r < 0 || n < r) {
        return 0;
    }
    ll ret = kai[n];
    ret *= fkai[r];
    ret %= m;
    ret *= fkai[n - r];
    ret %= m;
    return ret;
}

int LCA(const VVi& par, const Vi& depth, int a, int b)
{
    if (depth[a] < depth[b]) {
        swap(a, b);
    }
    int dis = depth[a] - depth[b];
    for (int i = 19; i >= 0; i--) {
        if ((dis >> i) & 1) {
            a = par[i][a];
        }
    }
    if (a == b) {
        return a;
    }
    for (int i = 19; i >= 0; i--) {
        if (par[i][a] != par[i][b]) {
            a = par[i][a];
            b = par[i][b];
        }
    }
    return par[0][a];
}

void dijkstra(const VVi& gr, const VVl& cost, Vl& dist, int s)
{
    ll INF = (ll)1e18;
    dist.assign(gr.size(), INF);
    dist[s] = 0;
    PQmin<Pl> pque;
    pque.push(make_pair(0, s));
    while (!pque.empty()) {
        auto [L, u] = pque.top();
        pque.pop();
        while (L != dist[u] && !pque.empty()) {
            tie(L, u) = pque.top();
            pque.pop();
        }
        for (int i = 0; i < gr[u].size(); i++) {
            int v = gr[u][i];
            ll c = cost[u][i];
            if (dist[v] > c + L) {
                dist[v] = c + L;
                pque.push(make_pair(dist[v], v));
            }
        }
    }
    return;
}
0