#969995 (C++23) No.2717 Sum of Subarray of Subsequence

• 問題: No.2717 Sum of Subarray of Subsequence
• ユーザー: Astral__
• 提出日時: 2024-04-05 22:58:25
• 言語: C++23 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 85 ms / 2,000 ms
• コード長: 17,375 bytes
• コンパイル時間: 3,461 ms
• コンパイル使用メモリ: 251,968 KB
• 実行使用メモリ: 8,064 KB
• 最終ジャッジ日時: 2024-10-01 02:57:38
• 合計ジャッジ時間: 5,685 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	2 ms; 5,248 KB
testcase_03	AC	2 ms; 5,248 KB
testcase_04	AC	1 ms; 5,248 KB
testcase_05	AC	1 ms; 5,248 KB
testcase_06	AC	1 ms; 5,248 KB
testcase_07	AC	1 ms; 5,248 KB
testcase_08	AC	2 ms; 5,248 KB
testcase_09	AC	79 ms; 7,936 KB
testcase_10	AC	78 ms; 8,064 KB
testcase_11	AC	79 ms; 7,808 KB
testcase_12	AC	78 ms; 7,936 KB
testcase_13	AC	79 ms; 7,808 KB
testcase_14	AC	78 ms; 7,936 KB
testcase_15	AC	78 ms; 7,808 KB
testcase_16	AC	78 ms; 7,808 KB
testcase_17	AC	79 ms; 7,936 KB
testcase_18	AC	82 ms; 7,936 KB
testcase_19	AC	85 ms; 7,936 KB
testcase_20	AC	2 ms; 5,248 KB
testcase_21	AC	2 ms; 5,248 KB
testcase_22	AC	82 ms; 7,936 KB
testcase_23	AC	70 ms; 7,808 KB

ソースコード

//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
//using uLL = unsigned __int128;
template <typename T> 
using pqg = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using pq = priority_queue<T>;
template <typename T>
using vec = vector<T>;
using pll = pair<long long, long long>;
using pii = pair<int, int>;
using vvvvl = vector<vector<vector<vector<ll>>>>;
using vvvi = vector<vector<vector<int>>>;
using vvvl = vector<vector<vector<ll>>>;
using vvvc = vector<vector<vector<char>>>;
using vvvd = vector<vector<vector<double>>>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvc = vector<vector<char>>;
using vvp = vector<vector<pair<ll, ll>>>;
using vvb = vector<vector<bool>>;
using vvd = vector<vector<double>>;
using vp = vector<pair<ll, ll>>;
using vi = vector<int>;
using vl = vector<ll>;
using vu = vector<unsigned long long>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
#define vvvm  vector<vector<vector<mint>>>
#define vvm  vector<vector<mint>>
#define vm  vector<mint>
template <typename T1, typename T2>
using umap = unordered_map<T1, T2>;
template <typename T>
using uset = unordered_set<T>;
#define rep(i, s, f) for(long long i = s; i <= f; i++)
#define rep1(i, s, f) for(long long i = s; i <= f; i++)
#define per(i, s, f) for(long long i = s; i >= f; i--)
#define per1(i, s, f) for(long long i = s; i >= f; i--)
#define all0(x) (x).begin() ,(x).end()
#define all(x) (x).begin() + 1, (x).end()
#define ins(x, l, r) (l <= x && x <= r)
#define ENDL '\n'
////////////////////////////////////////////////////////////////////////////////////////////////////////////
//これが本当の組み込み関数ってね（笑）
template <typename T>
int LB(vector<T> &A, T x) {
    return lower_bound(A.begin(), A.end(), x) - A.begin();
}

template <typename T>
int UB(vector<T> &A, T x) {
    return upper_bound(A.begin(), A.end(), x) - A.begin();
}
template <typename T>
void UNIQUE(vector<T> &A, int indexed) {
    sort(A.begin() + indexed, A.end());
    A.erase(unique(A.begin() + indexed, A.end()), A.end());
}
int msb(long long a) {
    if(a == 0) return -1;
    return 64 - int(__builtin_clzll(a));
}
template<typename T = long long>
void chmin(T &a, T b) {
    a = min(a, b);
}
template<typename T = long long>
void chmax(T &a, T b) {
    a = max(a, b);
}
//////////////////////////////////////////////////////////////////////
//数学系
///////////////////////////////////////////////////////////////////////
ll extgcd (ll a, ll b,  ll &x, ll &y) {
    if(b == 0) { x = 1;y = 0;return a;}
    ll d = extgcd(b, a%b, y, x);
    y -= a/b * x;
    return d;
}
template <typename T>
T ceil__(T a, T b) {
    assert(b != 0);
    if(a % b == 0) return a / b;
    if((a <= 0 && b < 0) || (a >= 0 && b > 0)) return a/b + 1;
    else return a / b;
}
template <typename T>
T floor__(T a, T b) {
    assert(b != 0);
    if(a % b == 0) return a / b;
    if((a <= 0 && b < 0) || (a >= 0 && b > 0)) return a/b;
    else return a/b - 1;
}
ll modpow(ll x, ll y, ll mod) {
    if(x > mod) x %= mod;
    if(y == 0) return 1;
    ll res = modpow(x, y >> 1, mod);
    res = res * res % mod;
    if(y & 1) res *= x, res %= mod;
    return res;
}
ll sqrt__(ll a) {
    ll l = 0;
    ll r = 3037000499LL;
    while(l < r) {
        ll mid = (l + r + 1) / 2;
        if(mid * mid <= a) l = mid;
        else r = mid - 1;
    }
    return l;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//グローバル変数を置くところ
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize "trapv" //お祈り。変数同士の演算でのみ感知。代入や、 a *= 10000 では感知しない。
const ll big = 1001001001;
const ll BIG = 1001001001001001001LL;
const double pi = 3.141592653589793;
vl dx{0, 1, 0, -1, 0, 1, 1, -1, -1};  // 座標平面において、(番兵) → ↓ ← ↑  ※ 右から時計回り 注 : グリッド or 座標で上下は反転する。
vl dy{0, 0, -1, 0, 1, 1, -1, -1, 1};
//const ll mod = 1000000007;
//const ll mod = 998244353;
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

struct mint{//998244353
    long long x;
    static const long long mod = 998244353;
    mint(long long _x=0) noexcept : x((_x%mod+mod)%mod){}
    long long val() const noexcept {return x;}
    mint& operator+=(const mint& a) noexcept {if((x += a.x) >= mod) x -= mod;return *this;}
    mint& operator-=(const mint& a) noexcept {if((x += mod - a.x) >= mod) x -= mod;return *this;}
    mint& operator*=(const mint& a) noexcept {(x *= a.x) %= mod;return *this;}
    mint& operator/=(const mint& a) {return (*this) *= a.inv();}
    mint& operator++() noexcept {return *this += 1;}
    mint& operator--() noexcept {return *this -= 1;}
    mint operator++(int) {mint tmp = *this; ++*this; return tmp;}
    mint operator--(int) {mint tmp = *this; --*this; return tmp;}
    mint inv() const {return pow(mod-2);}
    friend mint operator+(const mint&  t, const mint& a)  {mint tmp = t; return tmp += a;}
    friend mint operator-(const mint&  t, const mint& a)  {mint tmp = t; return tmp += (a * -1);}
    friend mint operator*(const mint&  t, const mint& a)  {mint tmp = t; return tmp *= a;}
    friend mint operator/(const mint&  t, const mint& a)  {assert(a.x != 0) ; return a.inv() *=  t;}
    mint pow(const long long& y) const {
        if(!y) return 1;
        mint res = pow(y >> 1);
        res *= res;
        if(y & 1) res *= *this;
        return res;
    }
    friend istream& operator>>(istream& is, mint& a) { return is >> a.x;}
    friend ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
    bool operator==(const mint& a) const {return x == a.x;}
    bool operator!=(const mint& a) const {return x != a.x;}
    bool operator<(const mint& a) const {return x < a.x;}
};

void solve() {
	ll N;
	cin >> N;
	vl A(N+1, 0);
	rep(i,1,N) cin >> A[i];
	vm dp(N+1, 0);
	vm dp2(N+1, 0);

	rep(i,1,N) {
		mint k = 0;
		if(i>=2) k += mint(i-1) * (mint(2).pow(i-2));
		k += mint(2).pow(i-1);
		k *= A[i];		
		dp[i] = dp[i-1]*2 + dp2[i-1] + k;
		dp2[i] = dp2[i-1]*2 + k;
	}

	cout << dp[N] << endl;

 
    

    
    

}



int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout << fixed << setprecision(15);
    ll T = 1;
    //cin >> T;
    rep(i, 1, T) {
        solve();
    }
    return 0;
}



/*

- WA : 違法な読み替えをしていないか・違法な操作をしていないか
・実装が重そうな時は確認する 一度飛ばしても良い
・嘘を吐いていないかの他に、違法な操作をしていないかもチェックする。特にふわっとした操作は危ない
  -区間をちょっと伸ばす←端の時、伸ばす余地はある。
  -選択肢のうち、どれでも良いから消す←本当にどれでも良いか 場合分けを挟んでないか そもそも消せる要素は存在するか
  -適当に割り振る←順番を区別する必要があるかもしれない
・dpで途中までは辻褄が合っても、最後に分岐するので纏めてはいけない遷移というのがある



[整理パート] とりあえずやること
・必ずやらなければいけない操作は、順番が許すなら最初にやる
・確実にかかる費用があるなら、その費用は確定した上で他にかかる費用を最小化する。
・要素と制約をグラフで表してみる
  -関係がある要素間を辺で結び、制約上独立な要素集合ごとに見る
  -遷移を図で表現し、使いまわしたりできないか見る
・制約を「全ての要素についてoo ⇔ (1<=i<=N)で、iについてoo」といったように、独立なものに言い換えた方がやりやすいこともある
  -特に、bit演算が絡む時は、整数をbit毎に見る事で1つの制約を扱いやすい制約30個に分解できる(bit演算以外の時は、この30個が複雑に絡み合う可能性が高くなる)
・操作を制約に合わせて言い換える・制約を操作に合わせて言い換える。言い換えない方が良いことは多々ある。
  -全てがの要素が等しい⇔差分列が全て0
  -階差数列⇔差分列の要素の値が等しい
  -配列の、まとまった領域に対するよく分からない操作は(1)何ができるか調べる(2)何が作れるのか調べる(3)差分列に注目(4)modMごとに分けてみる(5)累積和列に注目

・制約・与えられた操作を、実際の操作・構築の手順に言い換える。
  -無駄な事/非効率な事は禁止して、その上で何ができるか・有効な遷移はどの様にまとめられるかをみる。本質が見えやすくなる
    ・何ができるか？が一旦整理できたが、それでも最適な操作の順・或いは数え上げの方法がわからない→どの様な答えなら作れるか？
  -制約を違反する様な操作・構築を禁止。結局やって良い操作・構築はどの様なものかを見る←本質が見えやすくなる
  -条件を満たす限りにおいて、自由度が高い構築の方が他の制約を満たしやすい
  -後から調整を入れやすいやつは後回し。全体を特徴づけるのは先に満たす。
  -この構築で可能か？を探る際は、最悪ケースで実験する。穴がある解を未然に防ぐ。

・よくわからないもの・扱いづらいものを言い換える。
  -特に、慣れ親しんだ制約も、問題設定によってより扱いやすい形に言い換えられるかもしれない（例：グラフが連結)
・強い制約は、数え上げ・最適化・クエリ・ゲーム共に良い性質を生みやすいので注目する
  -制約に具体的な数値が登場している←適当に解をいじると何となく性質が見えることが多い
  -強い言葉を使われた・補集合が単純なものを提示されたら、ほう助を疑う。 
     -「値がxに一致しない」
     -「1つ以上存在する・1つも存在しない」
     -「1回以上発生する・1度も発生しない」
     

[観察]  様々な解法も、実際試さないとそれで解けると分からないことは多い。
[]それらしい筋を書いておく → 一本道でもない限り、それぞれの解法をある程度並行して考える。 また、困ったら全部の筋を試す。
  -特に、最初に建てた方針は等しく皆大事にする。1つにのめり込むことのない様に。
[]１5分毎ぐらいに進捗を確認する←考察が進んでいない・闇雲な無限整理編に入っていたら、その筋はやばい可能性が高いので他の筋があれば変える。あるいは飛ばす。
	-数学的な式を満たす値は、グラフを書いたり列挙をすることで性質が見えることもある。
  -数学的な求値は、意味づけによる計算量削減が難しいが、漸化式的な発想が役に立つことが多い。
    ・combinationが入るΣ
  -なんか強そうな制約がある時、そいつが良い性質を持つことがある。
    -明らかに小さい数字
	-満たすものが少なそうな制約は、同時に探索空間も小さくできるかも
  -問題設定によって、探索空間そのものが狭くなっている場合がある。


[やる事ない]
・取れる選択肢がある限り全て試す。一つに固執せず、横断的に見る。
・過去の問題の手法を当てはめてみる。
・逆に、何ができる・成り立っているなら問題を解けるかを考える。それが実際できることを疑う。
  -大胆予想が正しい
    ・大胆予想：特殊ケース（c=0等)の時の答えと、一般のケースの答えが一致する
    ・大胆予想：必要十分条件がooである


[やる事ない：数え上げ周り] どれかに当てはまれば、解ける。そして、だいたいどれか。
[1]探索空間に特徴がある [2]解に特徴がある [3]探索順を変える [4]全探索の対象を全て試す
  -[3]でかい方から、深い方から、DAGで先端になっている・或いは葉になっている所から、全てを逆に言い換えて時系列的に後ろから ... で、構造が単純になることがある。
  -[4]固定するものの数が多くても、何かを固定した時の場合の和が綺麗に表せれば、固定するものを纏めて計算できる。


[やる事ない：最適化周り]
[1]探索空間に特徴がある [2]解の形を絞れる [3]最悪ケース・最良ケースを纏めると、スコアに関わる本質部分がわかって、場合分けが進む/上界・下界が絞れる。 [4]探索順を変える [5]探索の軸を変える [6]特殊ケースの解方が一般ケースでも最適 [7]自由度を無視しても最適解が構築できる 
  -[3]最悪・最良の疑いがある解を見つけたら、最悪である必要条件を考えて、最悪ケースを特徴づけする。その後、２番目に最悪ケースについて同じことをしたり、他のケースに含まれる部分的な最悪ケースが支配的になっていることを考える。
  -[4]でかい方から、深い方から、DAGで先端になっている・或いは葉になっている所から、全てを逆に言い換えて時系列的に後ろから ... で、貪欲が見えたり構造が単純になることがある。
  -[5]今給油するか？では無く、「ここで必要なガソリンはどこで給油するか？
・「最適な操作順」や「操作順に関する貪欲」なんてわからないという時、一旦引いて「ooの分のコストは確実にかかる」等を整理すると、手順を陽に明かさずとも最適な答えがわかることはある。
・bit演算がメインなら、bitごとにみる。特に、msbに注目する。（数が少ないので必要条件になりやすい・大きくする時の貪欲はとにかく上を立てる)
・関係をグラフに起こしてあると気づきやすいこともある
    -2部グラフが絡むこともある
・差分を計算するなら、最初から差分計算の処理のみ[で答えを計算した方が良い。最初を愚直でやると情報をロストする可能性があるし、愚直の枠組みに囚われる事もある。


[やる事ない：クエリ]
[1]1回のクエリが高速に計算できる [2]差分が計算できる [3]最終的に求める値がそれぞれ高速に計算できる [4]最終的に求める値が並列に計算できる 
  -[1]確かに1回のクエリが解けた事を確認してから更新を考える事  解ける前から「直観的に必要そうな情報」の更新を考えたりしない (制約を元に、計算量をメタ読みするのは良い)

[やる事ない：操作列の長いシュミレーション周り]
[0]計算の軸を変える [1]周期性がある [2]再帰的に計算できる [3]時間のかかる操作の回数が少ない   
  -[0]...操作を順々にしていくのでは無く、求めるものを直接求めにいく
  -[1],[2] 綺麗な構造になっていれば
  -[3]...シュミレーションを実行するのに必要な計算を列挙する。重いやつのうち、実際にやらなければならない回数が実は少ないなど。

-一つの解法で駄目な時、周辺の解法も試すようにする。周辺で見えないなら全部試す。
・「順々に操作をしていく」と「対象の必要条件から見る」 また、操作のどれを1段階とするかは自由に決めて良い(DPと同じ)。特に、操作をさらに細かくすることで1回を軽くすることもある。
  -「操作をしながら数え上げていく」と「数える対象必要条件をみる・特徴づけをする」
  -「(削除の)シュミレーションを高速にやる」と「要素が最後まで残る必要条件をみる」
・「貪欲で最適解」と「解の形を絞って全探索」
・「dp/最適化」と「解の形を絞って全探索」と 上界を見積もる」
・「dp」と「必要な情報を言い換える・何でのその情報が必要なのか考える事による高速化」
・「全探索」と「軸を変えた全探索」
・「全探索する軸が違うのに計算量同じな解法のペアがある」 と 「それぞれに得意・貪欲によりさらに計算量を減らせる範囲だけを計算させることでO(N√N)
  -自由度が2つ以上あるときなど 例：「数列が等差数列である ... 「一つ、数列の値を指定する」と「公差を指定する」

・「答えの個数・値が小さい」と「探索範囲をせばせて良い」
・「bit/素因数ごとに分ける」と「分けずにまとめて計算する」

*/