#1153558 (C++23) No.3473 AtCoder < CMS

• 問題: No.3473 AtCoder < CMS
• ユーザー: ルビサファせだい
• 提出日時: 2026-03-23 12:58:56
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 3,160 bytes
• コンパイル時間: 5,423 ms
• コンパイル使用メモリ: 374,884 KB
• 実行使用メモリ: 6,272 KB
• 最終ジャッジ日時: 2026-03-23 12:59:08
• 合計ジャッジ時間: 11,509 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 1
other	AC * 20

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using i128 = __int128;
using pll = pair<ll, ll>;
using vll = vector<ll>;
template <class T>
using max_heap = priority_queue<T>;
template <class T>
using min_heap = priority_queue<T, vector<T>, greater<>>;

constexpr ll INF = (1LL << 60);
ll ALPHABET_N = 26;
#define rep(i, n) for (ll i = (ll)0; i < (ll)n; i++)
#define rep_(i, k, n) for (ll i = (ll)k; i < (ll)n; i++)
#define rrep(i, n) for (ll i = (ll)(n) - 1; i >= 0; i--)
#define all(a) a.begin(), a.end()

template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}

template <class T>
bool chmin(T &a, const T &b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}

#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;

// comb_mint.hpp
#include <vector>
#include <atcoder/modint>

template <class Mint = atcoder::modint998244353>
struct CombMint {
    // fac[i] = i!, finv[i] = (i!)^{-1}, inv[i] = i^{-1}
    std::vector<Mint> fac, finv, inv;

    CombMint(int n = 0) {
        fac  = {Mint(1)};     // 0! = 1
        finv = {Mint(1)};     // (0!)^{-1} = 1
        inv  = {Mint(0)};     // 0 の逆元は未定義なので 0 で埋めておく（使わない）
        if (n > 0) ensure(n);
    }

    // 必要なサイズまでテーブルを拡張（O(n)）
    void ensure(int n) {
        int cur = (int)fac.size() - 1;
        if (n <= cur) return;

        fac.resize(n + 1);
        finv.resize(n + 1);
        inv.resize(n + 1);

        // まず factorial を伸ばす
        for (int i = cur + 1; i <= n; ++i) fac[i] = fac[i - 1] * i;

        // finv[n] = (n!)^{-1} を 1 回だけ inv() で取り、あとは降順で展開
        finv[n] = fac[n].inv();
        for (int i = n; i > 0; --i) finv[i - 1] = finv[i] * i;

        // inv[i] = i^{-1} を O(1) で復元（i >= 1）
        for (int i = std::max(1, cur + 1); i <= n; ++i) inv[i] = finv[i] * fac[i - 1];
    }

    // nCm（n から m 個選ぶ）：m<0 や m>n は 0
    Mint C(long long n, long long m) {
        if (m < 0 || m > n) return Mint(0);
        int need = (int)n;
        ensure(need);
        return fac[n] * finv[m] * finv[n - m];
    }

    // nHm（重複組合せ）：n 種から重複を許して m 個
    // 通常の式 C(n + m - 1, m) を使用。n=0 のときは m==0 のみ 1。
    Mint H(long long n, long long m) {
        if (m < 0) return Mint(0);
        if (n == 0) return (m == 0) ? Mint(1) : Mint(0);
        long long N = n + m - 1;
        int need = (int)N;
        ensure(need);
        return C(N, m);
    }

    // 便利な別名
    Mint nCk(long long n, long long k) { return C(n, k); }
    Mint nHk(long long n, long long k) { return H(n, k); }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll t;
    cin>>t;
    rep(_,t) {
        ll n,m;
        cin>>n>>m;
        mint ans = (mint(2).pow(n) - 1).pow(m);
        mint minus = mint(2).pow(m).pow(n) - (mint(2).pow(m) - 1).pow(n);
        ans -= minus;
        cout<<ans.val()<<endl;
    }
    return 0;
}