https://natsugiri.hatenablog.com/entry/2025/02/11/221241

始めに

I1 は最短の長さを答えるEasy版。I2 はそれが何通りできるか数え上げるHard版。
codeforces.com

問

数列 a が与えられる。a は以下の条件を満たしていることが保証されている。

任意の i について、 $|a_i| \le \sum a$

次のような数列 b を作りたい。

b は部分列として a を含む（連続でなくても良い）
$\sum a = \sum b$
b における任意の連続部分列の和は $\sum b$ 以下である。つまり $\forall{(l, r)} \{ \sum_{i=l}^r b_i \le \sum b\}$

I1: b の最短の長さを求めよ。
I2: 最短の長さのbは何通りあるか998244353で割った余りを求めよ。（同じ b でも異なるインデックスの選び方の部分列でaが存在するなら、異なるものとしてカウントする）

解法

連続部分列の和が $\sum a$ となるような b ができる。さらに b のprefix sum は 0 以上 $\sum a$ 以下であることが分かる。
動的計画法を考えて、その特徴からスピードアップできることが分かる。

dp(i, s, p) := 
- a の接頭のi要素を使って bの接頭を作っていて
- bの接頭の和はsで
- pが0ならi要素を見た直後、pが1なら追加で新しい要素を入れるか検討した後
- そのときの最短の長さ

s < 0 または $\sum a$ < s の場合は最短は存在しないので無限大として良い。
dp(i, s, 0) から dp(i, s', 1) の遷移を考えると、末尾に適切な1要素を追加することで dp(i, s', 1) は dp(i, *, 0)の最小値プラス1以下に出来る。さらにdp(i, *, 1) の最小値の範囲は連続している。

解 I1: このdpテーブルのdp(n, sumA, 1)が求めるべき解であるが、求めるには途中の最小値の値とその範囲だけ計算すれば良い。

解 I2: このdpテーブルで最短を計算していたが（最短, 場合の数) を計算することにする。dp(i, *, 1) を Run-length で持てば良い。区間に加算する必要があるので差分を持つことにして回避する。

======

コード

// I1
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
#define rprintf(fmt, begin, end) do { const auto end_rp = (end); auto it_rp = (begin); for (bool sp_rp=0; it_rp!=end_rp; ++it_rp) { if (sp_rp) putchar(' '); else sp_rp = true; printf(fmt, *it_rp); } putchar('\n'); } while(0)

int N;
int A[3000011];

void MAIN() {
    scanf("%d", &N);
    REP (i, N) scanf("%d", A+i);

    LL target = 0;
    REP (i, N) target += A[i];

    LL l = 0, r = 0;
    int cost = 0;
    REP (i, N) {
	l += A[i];
	r += A[i];
	if (l <= target && 0 <= r) {
	    amax(l, 0LL);
	    amin(r, target);
	} else if (r < 0) {
	    l = 0;
	    r = target + A[i];
	    cost++;
	} else {
	    assert(target < l);
	    l = A[i];
	    r = target;
	    cost++;
	}
    }
    cost += N;
    if (r < target) {
	cost++;
    }
    printf("%d\n", cost);
}

int main() {
    int TC = 1;
    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}

// I2
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
#include<queue>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
#define rprintf(fmt, begin, end) do { const auto end_rp = (end); auto it_rp = (begin); for (bool sp_rp=0; it_rp!=end_rp; ++it_rp) { if (sp_rp) putchar(' '); else sp_rp = true; printf(fmt, *it_rp); } putchar('\n'); } while(0)
template<unsigned MOD_> struct ModInt {
    static constexpr unsigned MOD = MOD_;
    unsigned x;
    void undef() { x = (unsigned)-1; }
    bool isnan() const { return x == (unsigned)-1; }
    inline int geti() const { return (int)x; }
    ModInt() { x = 0; }
    ModInt(int y) { if (y<0 || (int)MOD<=y) y %= (int)MOD; if (y<0) y += MOD; x=y; }
    ModInt(unsigned y) { if (MOD<=y) x = y % MOD; else x = y; }
    ModInt(long long y) { if (y<0 || MOD<=y) y %= MOD; if (y<0) y += MOD; x=y; }
    ModInt(unsigned long long y) { if (MOD<=y) x = y % MOD; else x = y; }
    ModInt &operator+=(const ModInt y) { if ((x += y.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator-=(const ModInt y) { if ((x -= y.x) & (1u<<31)) x += MOD; return *this; }
    ModInt &operator*=(const ModInt y) { x = (unsigned long long)x * y.x % MOD; return *this; }
    ModInt &operator/=(const ModInt y) { x = (unsigned long long)x * y.inv().x % MOD; return *this; }
    ModInt operator-() const { return (x ? MOD-x: 0); }

    ModInt inv() const { return pow(MOD-2); }
    ModInt pow(long long y) const {
	ModInt b = *this, r = 1;
	if (y < 0) { b = b.inv(); y = -y; }
	for (; y; y>>=1) {
	    if (y&1) r *= b;
	    b *= b;
	}
	return r;
    }

    friend ModInt operator+(ModInt x, const ModInt y) { return x += y; }
    friend ModInt operator-(ModInt x, const ModInt y) { return x -= y; }
    friend ModInt operator*(ModInt x, const ModInt y) { return x *= y; }
    friend ModInt operator/(ModInt x, const ModInt y) { return x *= y.inv(); }
    friend bool operator<(const ModInt x, const ModInt y) { return x.x < y.x; }
    friend bool operator==(const ModInt x, const ModInt y) { return x.x == y.x; }
    friend bool operator!=(const ModInt x, const ModInt y) { return x.x != y.x; }
};

constexpr LL MOD = 998244353;
using Mint = ModInt<MOD>;

struct Elem {
    LL len;
    int cost;
    Mint value;
    Elem() {}
    Elem(LL len_, int cost_, Mint value_): len(len_), cost(cost_), value(value_) {}
};
deque<Elem> dq;
Mint C[3000011];
Mint offset[3000011];

void right_delete(LL n) {
    while (n) {
	int cost = dq.back().cost;
	Mint value = dq.back().value;
	LL g = min(n, dq.back().len);
	C[cost] -= g * (value + offset[cost]);

	dq.back().len -= g;
	n -= g;

	if (dq.back().len == 0) {
	    dq.pop_back();
	}
    }
}

void left_delete(LL n) {
    while (n) {
	int cost = dq.front().cost;
	Mint value = dq.front().value;
	LL g = min(n, dq.front().len);
	C[cost] -= g * (value + offset[cost]);

	dq.front().len -= g;
	n -= g;

	if (dq.front().len == 0) {
	    dq.pop_front();
	}
    }
}


int N;
int A[3000011];

void MAIN() {
    dq.clear();
    scanf("%d", &N);
    REP (i, N) scanf("%d", A+i);

    LL target = 0;
    REP (i, N) target += A[i];

    LL l = 0, r = 0;
    int cost = 0;
    dq.emplace_back(1, 0, Mint(1) - offset[0]);
    C[0] = 1;
    if (target) {
	dq.emplace_back(target, 1, Mint(1) - offset[1]);
	C[1] = target;
    }

    REP (i, N) {
	if (A[i] > 0) {
	    LL a = A[i];
	    right_delete(a);
	    if (target < l + a) {
		assert(C[cost] == 0);
		cost++;
		C[cost+1] = 0;
		l = a;
		r = target;
	    } else {
		l += a;
		r = min(r + a, target);
	    }
	    dq.emplace_front(a, cost + 1, -offset[cost + 1]);
	}
	if (A[i] < 0) {
	    LL a = -A[i];
	    left_delete(a);
	    if (r - a < 0) {
		cost++;
		C[cost+1] = 0;
		l = 0;
		r = target - a;
	    } else {
		r -= a;
		l = max(0LL, l - a);
	    }
	    dq.emplace_back(a, cost + 1, -offset[cost + 1]);
	}

	offset[cost + 1] += C[cost];
	C[cost + 1] += C[cost] * ((target + 1) - (r - l + 1));
    }

    Mint ans = dq.back().value + offset[dq.back().cost];
    printf("%d\n", ans.geti());
}

int main() {
    int TC = 1;
    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}