結果
問題 | No.3070 Collecting Coins Speedrun 2 |
ユーザー |
|
提出日時 | 2025-03-21 22:40:41 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 46 ms / 2,000 ms |
コード長 | 1,882 bytes |
コンパイル時間 | 6,098 ms |
コンパイル使用メモリ | 333,044 KB |
実行使用メモリ | 7,324 KB |
最終ジャッジ日時 | 2025-03-21 22:40:53 |
合計ジャッジ時間 | 7,075 ms |
ジャッジサーバーID (参考情報) |
judge7 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; #define rep(i, a, n) for(ll i = a; i < n; i++) #define rrep(i, a, n) for(int i = a; i >= n; i--) #define inr(l, x, r) (l <= x && x < r) #define ll long long #define ld long double // using mint = modint1000000007; using mint = modint998244353; constexpr int IINF = 1001001001; constexpr ll INF = 1e18; template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;} template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;} const int vmax = 200005; // ここは問題ごとに考慮が必要 mint fact[vmax], finv[vmax]; void initfact(){ fact[0]= 1; for(int i = 1; i < vmax; i++) fact[i] = fact[i-1]*i; // 階乗の計算 finv[vmax-1] = fact[vmax-1].inv(); for(int i = vmax-2; i >=0; i--) finv[i] = finv[i+1]*(i+1); // 階乗の逆元 } // nCk mint choose(int n,int k){ if(n < 0 || k < 0 || n < k) return 0; if(n == 0 && k == 0) return 1; return fact[n]*finv[n-k]*finv[k]; } // (a+b)!/(a!b!) mint binom(int a,int b){ return 0<=a&&0<=b?fact[a+b]*finv[a]*finv[b]:0; } // カタラン数(括弧列とか) mint catalan(int n){ return binom(n,n)-(n-1>=0?binom(n-1,n+1):0); } // 重複組み合わせ mint homogeneous(int n, int k){ return choose(n+k-1, k); } int main(){ initfact(); int n; cin >> n; vector<int> pos, zero, neg; rep(i, 0, n){ int c; cin >> c; if(c == 0) zero.push_back(c); if(c > 0) pos.push_back(c); if(c < 0) neg.push_back(c); } int cnt = 0; if(!zero.empty()) cnt++; if(!pos.empty()) cnt++; if(!neg.empty()) cnt++; mint ans = 1; if(cnt == 2) ans = 2; if(cnt == 3) ans = 6; if(!pos.empty()){ ans *= mint(2).pow((int)pos.size()-1); } if(!neg.empty()){ ans *= mint(2).pow((int)neg.size()-1); } cout << ans.val() << endl; return 0; }