結果
| 問題 | No.2792 Security Cameras on Young Diagram |
| ユーザー |
 k1suxu
|
| 提出日時 | 2024-06-22 14:48:27 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 34 ms / 2,000 ms |
| コード長 | 8,087 bytes |
| コンパイル時間 | 4,903 ms |
| コンパイル使用メモリ | 275,108 KB |
| 実行使用メモリ | 7,224 KB |
| 最終ジャッジ日時 | 2024-06-24 18:48:48 |
| 合計ジャッジ時間 | 6,126 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 21 |
ソースコード
#pragma GCC target("avx")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include <bits/stdc++.h>using namespace std;#define rep(i,n) for(int i = 0; i < (int)n; i++)#define FOR(n) for(int i = 0; i < (int)n; i++)#define repi(i,a,b) for(int i = (int)a; i < (int)b; i++)#define all(x) x.begin(),x.end()//#define mp make_pair#define vi vector<int>#define vvi vector<vi>#define vvvi vector<vvi>#define vvvvi vector<vvvi>#define pii pair<int,int>#define vpii vector<pair<int,int>>template<typename T>bool chmax(T &a, const T b) {if(a<b) {a=b; return true;} else {return false;}}template<typename T>bool chmin(T &a, const T b) {if(a>b) {a=b; return true;} else {return false;}}using ll = long long;using ld = long double;using ull = unsigned long long;const ll INF = numeric_limits<long long>::max() / 2;const ld pi = 3.1415926535897932384626433832795028;const ll mod = 998244353;int dx[] = {1, 0, -1, 0, -1, -1, 1, 1};int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};#define int long longtemplate<long long MOD>struct Modular_Int {using Mint_Type = Modular_Int<MOD>;long long x;Modular_Int() = default;Modular_Int(long long x_) : x(x_ >= 0? x_%MOD : (MOD-(-x_)%MOD)%MOD) {}long long val() const {return (x%MOD+MOD)%MOD;}static long long get_mod() {return MOD;}Mint_Type& operator^=(long long d) {Mint_Type ret(1);long long nx = x;while(d) {if(d&1) ret *= nx;(nx *= nx) %= MOD;d >>= 1;}*this = ret;return *this;}Mint_Type operator^(long long d) const {return Mint_Type(*this) ^= d;}Mint_Type pow(long long d) const {return Mint_Type(*this) ^= d;}//use this basicallyMint_Type inv() const {return Mint_Type(*this) ^ (MOD-2);}//only if the module number is not prime//Don't use. This is broken.// Mint_Type inv() const {// long long a = (x%MOD+MOD)%MOD, b = MOD, u = 1, v = 0;// while(b) {// long long t = a/b;// a -= t*b, swap(a, b);// u -= t*v, swap(u, v);// }// return Mint_Type(u);// }Mint_Type& operator+=(const Mint_Type other) {if((x += other.x) >= MOD) x -= MOD;return *this;}Mint_Type& operator-=(const Mint_Type other) {if((x -= other.x) < 0) x += MOD;return *this;}Mint_Type& operator*=(const Mint_Type other) {long long z = x;z *= other.x;z %= MOD;x = z;if(x < 0) x += MOD;return *this;}Mint_Type& operator/=(const Mint_Type other) {return *this = *this * other.inv();}Mint_Type& operator++() {x++;if (x == MOD) x = 0;return *this;}Mint_Type& operator--() {if (x == 0) x = MOD;x--;return *this;}Mint_Type operator+(const Mint_Type other) const {return Mint_Type(*this) += other;}Mint_Type operator-(const Mint_Type other) const {return Mint_Type(*this) -= other;}Mint_Type operator*(const Mint_Type other) const {return Mint_Type(*this) *= other;}Mint_Type operator/(const Mint_Type other) const {return Mint_Type(*this) /= other;}Mint_Type& operator+=(const long long other) {Mint_Type other_(other); *this += other_; return *this;}Mint_Type& operator-=(const long long other) {Mint_Type other_(other); *this -= other_; return *this;}Mint_Type& operator*=(const long long other) {Mint_Type other_(other); *this *= other_; return *this;}Mint_Type& operator/=(const long long other) {Mint_Type other_(other); *this /= other_; return *this;}Mint_Type operator+(const long long other) const {return Mint_Type(*this) += other;}Mint_Type operator-(const long long other) const {return Mint_Type(*this) -= other;}Mint_Type operator*(const long long other) const {return Mint_Type(*this) *= other;}Mint_Type operator/(const long long other) const {return Mint_Type(*this) /= other;}bool operator==(const Mint_Type other) const {return (*this).val() == other.val();}bool operator!=(const Mint_Type other) const {return (*this).val() != other.val();}bool operator==(const long long other) const {return (*this).val() == other;}bool operator!=(const long long other) const {return (*this).val() != other;}Mint_Type operator-() const {return Mint_Type(0LL)-Mint_Type(*this);}//-1: sqrtが存在しない//複数存在する場合どれを返すかは不明long long get_sqrt() const {long long a = val(), p = get_mod();if(a == 0) return 0;if(p == 2) return a;if(Mint_Type(a).pow((p - 1) >> 1).val() != 1) return -1;long long b = 1;while(Mint_Type(b).pow((p - 1) >> 1).val() == 1) ++b;long long e = 0, m = p - 1;while(m % 2 == 0) m >>= 1, ++e;long long x = Mint_Type(a).pow((m - 1) >> 1).val();long long y = a * (x * x % p) % p;(x *= a) %= p;long long z = Mint_Type(b).pow(m).val();while(y != 1) {long long j = 0, t = y;while(t != 1) {j += 1;(t *= t) %= p;}z = Mint_Type(z).pow((long long)1 << (e - j - 1)).val();(x *= z) %= p;(z *= z) %= p;(y *= z) %= p;e = j;}return x;}template <typename T>friend Mint_Type operator+(T t, const Mint_Type& o) {return o + t;}template <typename T>friend Mint_Type operator-(T t, const Mint_Type& o) {return -o + t;}template <typename T>friend Mint_Type operator*(T t, const Mint_Type& o) {return o * t;}template <typename T>friend Mint_Type operator/(T t, const Mint_Type& o) {return o.inv() * t;}};// TODO: SELECT MOD_VAL// const long long MOD_VAL = 1e9+7;const long long MOD_VAL = 998244353;using mint = Modular_Int<MOD_VAL>;istream& operator>>(istream& is, mint& x) {long long X;is >> X;x = X;return is;}ostream& operator<<(ostream& os, mint& x) {os << x.val();return os;}// 1e9 + 7をmodとして使いたいときに注意！！！！特にCFやCCなどのAtCoder以外vector<mint> fact = {1}, fact_inv = {1};void factor_init(long long n) {++n;fact.resize(n, 0);fact_inv.resize(n, 0);fact[0] = 1;repi(i, 1, n) fact[i] = (fact[i - 1] * i);fact_inv[n-1] = fact[n-1].inv();for(int i = n-1; i > 0; --i) fact_inv[i-1] = fact_inv[i] * i;}mint P(long long n, long long k) {if(n<k) {cerr << "\nAssertion Failed!!\n";cerr << "Expression N >= K, ";cerr << "where n=" << n << ",k=" << k << "\n\n";return 0;}while(n > fact.size()-1) {fact.push_back(fact.back() * fact.size());fact_inv.push_back(fact.back().inv());}return fact[n] * fact_inv[n-k];}mint C(long long n, long long k) {if(n<k) {cerr << "\nAssertion Failed!!\n";cerr << "Expression N >= K, ";cerr << "where n=" << n << ",k=" << k << "\n\n";return 0;}while(n > fact.size()-1) {fact.push_back(fact.back() * fact.size());fact_inv.push_back(fact.back().inv());}return fact[n]*fact_inv[n-k]*fact_inv[k];}mint H(long long n, long long k) {assert(n>=1);return C(n+k-1, k);}mint Cat(long long n) {return C(2*n, n)-C(2*n, n-1);}void solve() {const int MX = 2e5;int n;cin >> n;vi a(n+1);FOR(n) cin >> a[i];a[n] = 0;mint ans = 0;FOR(n) repi(j, a[i+1]+1, a[i]+1) ans += C(i+j-1, i);vi tot(MX+1);FOR(n) tot[a[i]]++;for (int i = MX; i > 0; i--) tot[i-1] += tot[i];FOR(MX) repi(j, tot[i+1]+1, tot[i]+1) ans += C(i+j-2, i-1);cout << ans << endl;}signed main() {cin.tie(nullptr);ios::sync_with_stdio(false);solve();return 0;}