結果

問題 No.2130 分配方法の数え上げ mod 998244353
ユーザー akinyanakinyan
提出日時 2022-11-25 21:35:47
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 6,456 bytes
コンパイル時間 4,086 ms
コンパイル使用メモリ 291,572 KB
実行使用メモリ 8,192 KB
最終ジャッジ日時 2024-04-10 02:48:10
合計ジャッジ時間 8,290 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 18 ms
7,936 KB
testcase_01 AC 18 ms
8,064 KB
testcase_02 AC 16 ms
7,936 KB
testcase_03 AC 16 ms
7,936 KB
testcase_04 AC 16 ms
7,936 KB
testcase_05 AC 17 ms
8,192 KB
testcase_06 AC 17 ms
7,936 KB
testcase_07 AC 16 ms
7,936 KB
testcase_08 AC 17 ms
8,192 KB
testcase_09 AC 17 ms
7,936 KB
testcase_10 AC 16 ms
7,936 KB
testcase_11 AC 16 ms
7,936 KB
testcase_12 AC 17 ms
8,064 KB
testcase_13 AC 16 ms
8,064 KB
testcase_14 AC 16 ms
7,936 KB
testcase_15 AC 16 ms
7,936 KB
testcase_16 AC 15 ms
7,936 KB
testcase_17 AC 17 ms
8,064 KB
testcase_18 AC 17 ms
7,936 KB
testcase_19 AC 17 ms
8,064 KB
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ch = char;
using ll = long long;
using ld = long double;
using db = double;
using st = string;
using vdb = vector<db>;
using vvdb = vector<vdb>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vd = vector<ld>;
using vvd = vector<vd>;
using vs = vector<st>;
using vvs = vector<vs>;
using vc = vector<ch>;
using vvc = vector<vc>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
const ll mod = 998244353;
const ll MOD = 1000000007;
const ll INF = 1000000000000000000LL;
using pall = pair<ll,ll>;
using vp = vector<pall>;

void fix(){
  cout<<fixed<<setprecision(20);
}
vl fact,inv_fact,inv;
void init(const ll MAX, ll m) {
    fact.resize(MAX);
    inv_fact.resize(MAX);
    inv.resize(MAX);
    fact[0] = 1;
    fact[1] = 1;
    inv[0] = 1;
    inv[1] = 1;
    inv_fact[0] = 1;
    inv_fact[1] = 1;
    for(int i=2; i<MAX; i++){
        fact[i] = fact[i - 1] * i % m;
        inv[i] = m - inv[m%i] * (m / i) % m;
        inv_fact[i] = inv_fact[i - 1] * inv[i] % m;
    }
}
ll nCk(ll n, ll k, ll m) {
    ll x = fact[n];
    ll y = inv_fact[n-k];
    ll z = inv_fact[k];
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return x * ((y * z) % m) % m;
}
// RMQ：[0,n-1] について、区間ごとの最小値を管理する構造体
//  set(int i, T x), build(): i番目の要素をxにセット。まとめてセグ木を構築する。O(n)
//  update(i,x): i 番目の要素を x に更新。O(log(n))
//  query(a,b): [a,b) での最小の要素を取得。O(log(n))
//  find_rightest(a,b,x): [a,b) で x以下の要素を持つ最右位置を求める。O(log(n))
//  find_leftest(a,b,x): [a,b) で x以下の要素を持つ最左位置を求める。O(log(n))
template <typename T>
struct RMQ {
    const T e = numeric_limits<T>::max();
    function<T(T, T)> fx = [](T x1, T x2) -> T { return min(x1,x2); };
    ll n;
    vector<T> dat;
    RMQ(ll n_) : n(), dat(n_ * 4, e) {
        ll x = 1;
        while (n_ > x) {
            x *= 2;
        }
        n = x;
    }
 
    void set(ll i, T x) { dat[i + n - 1] = x; }
    void build() {
        for (ll k = n - 2; k >= 0; k--) dat[k] = fx(dat[2 * k + 1], dat[2 * k + 2]);
    }
 
    void update(ll i, T x) {
        i += n - 1;
        dat[i] = x;
        while (i > 0) {
            i = (i - 1) / 2;  // parent
            dat[i] = fx(dat[i * 2 + 1], dat[i * 2 + 2]);
        }
    }
 
    // the minimum element of [a,b)
    T query(ll a, ll b) { return query_sub(a, b, 0, 0, n); }
    T query_sub(ll a, ll b, ll k, ll l, ll r) {
        if (r <= a || b <= l) {
            return e;
        } else if (a <= l && r <= b) {
            return dat[k];
        } else {
            T nl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
            T nr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
            return fx(nl, nr);
        }
    }
 
    ll find_rightest(ll a, ll b, T x) { return find_rightest_sub(a, b, x, 0, 0, n); }
    ll find_leftest(ll a, ll b, T x) { return find_leftest_sub(a, b, x, 0, 0, n); }
    ll find_rightest_sub(ll a, ll b, T x, ll k, ll l, ll r) {
        if (dat[k] > x || r <= a || b <= l) {  // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn a-1
            return a - 1;
        } else if (k >= n - 1) {  // 自分が葉ならその位置をreturn
            return (k - (n - 1));
        } else {
            int nr = find_rightest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
            if (nr != a - 1) {  // 右の部分木を見て a-1 以外ならreturn
                return nr;
            } else {  // 左の部分木を見て値をreturn
                return find_rightest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
            }
        }
    }
    ll find_leftest_sub(ll a, ll b, T x, ll k, ll l, ll r) {
        if (dat[k] > x || r <= a || b <= l) {  // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn b
            return b;
        } else if (k >= n - 1) {  // 自分が葉ならその位置をreturn
            return (k - (n - 1));
        } else {
            ll nl = find_leftest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
            if (nl != b) {  // 左の部分木を見て b 以外ならreturn
                return nl;
            } else {  // 右の部分木を見て値をreturn
                return find_leftest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
            }
        }
    }
};
ll modpow(ll a, ll n, ll m) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % m;
        a = a * a % m;
        n >>= 1;
    }
    return res;
}
ll modinv(ll a, ll b, ll m) {
    // a/bを返す
    return modpow(b, m - 2, m) * a % m;
}
vl zaatu(vl A){
    //0はじまり
    vl B=A;
    sort(B.begin(), B.end());
    B.erase(unique(B.begin(), B.end()), B.end());
    vl R(A.size());
    ll asize=A.size();
    for(int i=0; i<asize; i++){
        R[i] = lower_bound(B.begin(), B.end(), A[i]) - B.begin();
    }
    return R;
}
bool sosuu(ll a){
    for(ll i=2; i*i<=a; i++){
        if(a%i==0){
            return false;
        }
    }
    return true;
}
vl yakusuu(ll a){
    vl ANS;
    for(ll i=1; i*i<=a; i++){
        if(a%i==0){
            ANS.push_back(i);
            if(a/i!=i){
                ANS.push_back(a/i);
            }
        }
    }
    sort(ANS.begin(),ANS.end());
    return ANS;
}
ll yakusuu_kosuu(ll a){
    ll ans=0;
    for(ll i=1; i*i<=a; i++){
        if(a%i==0){
            ans++;
            if(a/i!=i){
                ans++;
            }
        }
    }
    return ans;
}
vp bunkai(ll N){
    vp res;
    for (long long a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long ex = 0;
        while (N % a == 0) {
            ++ex;
            N /= a;
        }
        res.push_back({a, ex});
    }
    if (N != 1) res.push_back({N, 1});
    return res;
}
ll ran(ll A,ll B){
    random_device a;
    mt19937 b(a());
    uniform_int_distribution<> c(A,B);
    return c(b);
}
ll mypow(ll a, ll n){
    ll ans=1;
    for(int i=0; i<n; i++){
        ans*=a;
    }
    return ans;
}
ll digsum(ll n) {
    ll res = 0;
    while(n > 0) {
        res += n%10;
        n /= 10;
    }
    return res;
}

int main(){
    init(200000,mod);
    ll N,M;
    cin>>N>>M;
    ll ans=0;
    for(int i=0; i<M; i++){
        ans+=nCk(N,i,mod);
        ans%=mod;
    }
    cout<<(modpow(2,N,mod)+mod-ans)%mod<<endl;
}
0