結果

問題 No.3476 {2^n-1}-gon
コンテスト
ユーザー Dipanshu
提出日時 2026-03-21 14:26:54
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 791 ms / 2,000 ms
コード長 990 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,057 ms
コンパイル使用メモリ 333,804 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2026-03-21 14:27:11
合計ジャッジ時間 10,461 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
int MOD = 998244353;

int binpow(int a, int p)
{
  if (p==0) return 1;
  if (p%2) return binpow(a,p-1)*a%MOD;
  int t=binpow(a,p/2);
  return t*t%MOD;
}

int inv(int a)
{
  return binpow(a,MOD-2);
}

int ncr(int n, int r)
{
  int rl = 1;
  for (int i = 1; i <= r; i++)
  {
    rl=(rl*(n-(i-1+MOD)%MOD+MOD)%MOD)%MOD;
    rl = (rl * inv(i))%MOD;
  }
  return rl;
}

void solve()
{
  int n,m;
  cin>>n>>m;
  
  if (n>=22 || (binpow(2,n)/2 + 1)>m)
  {
    // cout << " OR HERE " << endl;
    int A = ncr(binpow(2,n)-1, m);
    int B = binpow(2,n)*inv(2)%MOD;
    int C = ncr(B-1,m-1);
    // cout << A << " " << B << " " << C << endl;
    cout << (A - ((binpow(2,n)-1+MOD)%MOD*C)%MOD + MOD)%MOD << endl;
  }
  else
  {
    // cout <<  " HERE " << endl;
    cout << ncr(binpow(2,n)-1,m) << endl;
  }
}

signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  
  // int t;cin>>t;while(t--)
  solve();
}
0