結果
問題 | No.2792 Security Cameras on Young Diagram |
ユーザー |
👑 ![]() |
提出日時 | 2024-06-21 21:34:59 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 15 ms / 2,000 ms |
コード長 | 2,635 bytes |
コンパイル時間 | 1,087 ms |
コンパイル使用メモリ | 103,044 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-24 18:44:11 |
合計ジャッジ時間 | 1,903 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#ifdef NACHIA#define _GLIBCXX_DEBUG#else#define NDEBUG#endif#include <iostream>#include <string>#include <vector>#include <algorithm>#include <utility>#include <queue>#include <array>#include <cmath>#include <atcoder/modint>using i64 = long long;using u64 = unsigned long long;#define rep(i,n) for(int i=0; i<int(n); i++)#define repr(i,n) for(int i=int(n)-1; i>=0; i--)const i64 INF = 1001001001001001001;const char* yn(bool x){ return x ? "Yes" : "No"; }template<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; }template<typename A> void chmax(A& l, const A& r){ if(l < r) l = r; }template<typename A> using nega_queue = std::priority_queue<A,std::vector<A>,std::greater<A>>;using Modint = atcoder::static_modint<998244353>;//#include "nachia/vec.hpp"namespace nachia{template<class Modint>class Comb{private:std::vector<Modint> F;std::vector<Modint> iF;public:void extend(int newN){int prevN = (int)F.size() - 1;if(prevN >= newN) return;F.resize(newN+1);iF.resize(newN+1);for(int i=prevN+1; i<=newN; i++) F[i] = F[i-1] * Modint::raw(i);iF[newN] = F[newN].inv();for(int i=newN; i>prevN; i--) iF[i-1] = iF[i] * Modint::raw(i);}Comb(int n = 1){F.assign(2, Modint(1));iF.assign(2, Modint(1));extend(n);}Modint factorial(int n) const { return F[n]; }Modint invFactorial(int n) const { return iF[n]; }Modint invOf(int n) const { return iF[n] * F[n-1]; }Modint comb(int n, int r) const {if(n < 0 || n < r || r < 0) return Modint(0);return F[n] * iF[r] * iF[n-r];}Modint invComb(int n, int r) const {if(n < 0 || n < r || r < 0) return Modint(0);return iF[n] * F[r] * F[n-r];}Modint perm(int n, int r) const {if(n < 0 || n < r || r < 0) return Modint(0);return F[n] * iF[n-r];}Modint invPerm(int n, int r) const {if(n < 0 || n < r || r < 0) return Modint(0);return iF[n] * F[n-r];}Modint operator()(int n, int r) const { return comb(n,r); }};} // namespace nachiausing namespace std;void testcase(){int N; cin >> N;vector<int> A(N); rep(i,N) cin >> A[i];int M = A[0];vector<int> B(M);rep(i,N) B[A[i]-1] = i+1;repr(i,M-1) chmax(B[i], B[i+1]);auto comb = nachia::Comb<Modint>(N+M);Modint ans = 0;rep(i,N) ans += comb(i+A[i]-1, i);rep(i,M) ans += comb(i+B[i]-1, i);cout << ans.val() << endl;}int main(){ios::sync_with_stdio(false); cin.tie(nullptr);testcase();return 0;}