結果
問題 | No.1294 マウンテン数列 |
ユーザー |
![]() |
提出日時 | 2020-11-26 15:13:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 688 ms / 2,000 ms |
コード長 | 6,914 bytes |
コンパイル時間 | 2,109 ms |
コンパイル使用メモリ | 126,676 KB |
最終ジャッジ日時 | 2025-01-16 05:49:41 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include<iostream>#include<array>#include<string>#include<cstdio>#include<vector>#include<cmath>#include<algorithm>#include<functional>#include<iomanip>#include<queue>#include<ciso646>#include<random>#include<map>#include<set>#include<complex>#include<bitset>#include<stack>#include<unordered_map>#include<utility>#include<tuple>#include<cassert>using namespace std;typedef long long ll;typedef unsigned int ui;const ll mod = 998244353;const ll INF = (ll)1000000007 * 1000000007;typedef pair<int, int> P;#define stop char nyaa;cin>>nyaa;#define rep(i,n) for(int i=0;i<n;i++)#define per(i,n) for(int i=n-1;i>=0;i--)#define Rep(i,sta,n) for(int i=sta;i<n;i++)#define Per(i,sta,n) for(int i=n-1;i>=sta;i--)#define rep1(i,n) for(int i=1;i<=n;i++)#define per1(i,n) for(int i=n;i>=1;i--)#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)typedef long double ld;const ld eps = 1e-8;const ld pi = acos(-1.0);typedef pair<ll, ll> LP;int dx[4]={1,-1,0,0};int dy[4]={0,0,1,-1};template<class T>bool chmax(T &a, const T &b) {if(a<b){a=b;return 1;}return 0;}template<class T>bool chmin(T &a, const T &b) {if(b<a){a=b;return 1;}return 0;}template<int mod>struct ModInt {long long x;static constexpr int MOD = mod;ModInt() : x(0) {}ModInt(long long y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}explicit operator int() const {return x;}ModInt &operator+=(const ModInt &p) {if((x += p.x) >= mod) x -= mod;return *this;}ModInt &operator-=(const ModInt &p) {if((x += mod - p.x) >= mod) x -= mod;return *this;}ModInt &operator*=(const ModInt &p) {x = (int)(1LL * x * p.x % mod);return *this;}ModInt &operator/=(const ModInt &p) {*this *= p.inverse();return *this;}ModInt operator-() const { return ModInt(-x); }ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }ModInt operator%(const ModInt &p) const { return ModInt(0); }bool operator==(const ModInt &p) const { return x == p.x; }bool operator!=(const ModInt &p) const { return x != p.x; }ModInt inverse() const{int a = x, b = mod, u = 1, v = 0, t;while(b > 0) {t = a / b;a -= t * b;swap(a, b);u -= t * v;swap(u, v);}return ModInt(u);}ModInt power(long long n) const {ModInt ret(1), mul(x);while(n > 0) {if(n & 1)ret *= mul;mul *= mul;n >>= 1;}return ret;}ModInt power(const ModInt p) const{return ((ModInt)x).power(p.x);}friend ostream &operator<<(ostream &os, const ModInt<mod> &p) {return os << p.x;}friend istream &operator>>(istream &is, ModInt<mod> &a) {long long x;is >> x;a = ModInt<mod>(x);return (is);}};using modint = ModInt<mod>;template <class S, S (*op)(S, S), S (*e)()> struct SegmentTree {public:SegmentTree() : SegmentTree(0) {}SegmentTree(int n) : SegmentTree(std::vector<S>(n, e())) {}SegmentTree(const std::vector<S>& v) : _n(int(v.size())) {log = ceil_pow2(_n);size = 1 << log;d = std::vector<S>(2 * size, e());for (int i = 0; i < _n; i++) d[size + i] = v[i];for (int i = size - 1; i >= 1; i--) {update(i);}}void set_val(int p, S x) {assert(0 <= p && p < _n);p += size;d[p] = x;for (int i = 1; i <= log; i++) update(p >> i);}S get(int p) {assert(0 <= p && p < _n);return d[p + size];}S query(int l, int r) {assert(0 <= l && l <= r && r <= _n);S sml = e(), smr = e();l += size;r += size;while (l < r) {if (l & 1) sml = op(sml, d[l++]);if (r & 1) smr = op(d[--r], smr);l >>= 1;r >>= 1;}return op(sml, smr);}S all_query() { return d[1]; }template <bool (*f)(S)> int max_right(int l) {//f(op([l,r)))==trueを満たす最大のrreturn max_right(l, [](S x) { return f(x); });}template <class F> int max_right(int l, F f) {assert(0 <= l && l <= _n);assert(f(e()));if (l == _n) return _n;l += size;S sm = e();do {while (l % 2 == 0) l >>= 1;if (!f(op(sm, d[l]))) {while (l < size) {l = (2 * l);if (f(op(sm, d[l]))) {sm = op(sm, d[l]);l++;}}return l - size;}sm = op(sm, d[l]);l++;} while ((l & -l) != l);return _n;}template <bool (*f)(S)> int min_left(int r) {//f(op([l,r)))==trueを満たす最小のlreturn min_left(r, [](S x) { return f(x); });}template <class F> int min_left(int r, F f) {assert(0 <= r && r <= _n);assert(f(e()));if (r == 0) return 0;r += size;S sm = e();do {r--;while (r > 1 && (r % 2)) r >>= 1;if (!f(op(d[r], sm))) {while (r < size) {r = (2 * r + 1);if (f(op(d[r], sm))) {sm = op(d[r], sm);r--;}}return r + 1 - size;}sm = op(d[r], sm);} while ((r & -r) != r);return 0;}private:int _n, size, log;std::vector<S> d;void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }int ceil_pow2(int n) {int x = 0;while ((1U << x) < (unsigned int)(n)) x++;return x;}};int n;const int m=3000;int a[3010];modint Z[3010];modint f(modint a,modint b){return a+b;}modint e(){return 0;}void calc(int d){rep(i,n-1){if(a[i]-a[i+1]>d) return;}SegmentTree<modint,f,e> dp(a[0]+1);dp.set_val(a[0],1);Rep(i,1,n-1){dp.set_val(a[i],dp.query(a[i+1]+1,min(a[0]+1,a[i+1]+d+1)));}Z[d]=dp.query(0,a[0]+1)*(modint)2;}void solve(){cin >> n;rep(i,n) cin >> a[n-i-1];Rep(i,1,m) calc(i);modint ans=0;Rep(i,1,m){ans+=(modint)i*(Z[i]-Z[i-1]);}cout << ans << endl;}int main(){ios::sync_with_stdio(false);cin.tie(0);cout << fixed << setprecision(50);solve();}