結果

問題 No.3476 {2^n-1}-gon
コンテスト
ユーザー Dipanshu
提出日時 2026-03-21 14:26:54
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc15.so -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 582 ms / 2,000 ms
+ 665µs
コード長 990 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,394 ms
コンパイル使用メモリ 334,372 KB
実行使用メモリ 9,916 KB
最終ジャッジ日時 2026-10-22 11:33:16
合計ジャッジ時間 8,611 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge5_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

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