結果
問題 |
No.2802 Pill Bug in Grid Maze
|
ユーザー |
|
提出日時 | 2025-03-10 01:45:13 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 155 ms / 2,000 ms |
コード長 | 1,490 bytes |
コンパイル時間 | 6,676 ms |
コンパイル使用メモリ | 332,804 KB |
実行使用メモリ | 7,324 KB |
最終ジャッジ日時 | 2025-03-10 01:45:25 |
合計ジャッジ時間 | 11,542 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 31 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using mint = atcoder::static_modint<998244353>; // using mint = atcoder::static_modint<1000000007>; using ld = long double; using ll = long long; #define mp(a,b) make_pair(a,b) #define rep(i,s,n) for(int i=s; i<(int)n; i++) using vl = vector<ll>; using vvl = vector<vl>; using vvvl = vector<vvl>; using vvvvl = vector<vvvl>; const vector<int> dx{1,0,-1,0},dy{0,1,0,-1}; template<class T> struct Factorial{ Factorial(int _n):fac(_n+1,1),invfac(_n+1,1){ for(int i=1; i<=_n; i++){ fac[i]=fac[i-1]*i; invfac[i]/=fac[i]; } }; T nCr(int n,int r){ if(0<=r && r<=n)return fac[n]*invfac[r]*invfac[n-r]; else return 0; } T nPr(int n,int r){ if(0<=r && r<=n)return fac[n]*invfac[n-r]; else return 0; } T sum(int a,int b){ // \Sigma_{i\in[0,a],j\in[0,b]}(i+j)Ciを計算 return nCr(a+b+2,a+1)-1; } vector<T> fac,invfac; }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); const int m=500000; ll h,w;cin >> h >> w; Factorial<mint> F(m); if(min(h,w)==1){ cout << 1; return 0; } mint ans=0; rep(i,1,h+w+3){ if(h*w-(h+w-1)-(i-1)>=0)ans+=mint(2).pow(h*w-(h+w-1)-(i-1))*F.nCr(h-2,(i-1)/2)*F.nCr(w-1,i/2); // cout << (F.nCr(h-2,i/2)*F.nCr(w-1,(i+1)/2)).val() << " " << i << "\n"; } cout << ans.val(); }