E - NEQ and LEQ

题意

長さ $N$ の整数列 $A_1,A_2,\ldots,A_N$ が与えられます。長さ $N$ の整数列 $X_1,X_2,\ldots,X_N$ であって、以下の条件をすべて満たすものはいくつあるか求め、$998244353$ で割った余りを出力してください。

• $1\le X_i\le A_i$
• $X_i\neq X_{i+1}$ ($1\le i\le N-1$)

解析

设 $dp_i$ 表示前 $X_1,X_2,\ldots,X_i$ 的可行方案数。不难发现，$dp_j\min\limits_{j<k\le i}A_k$ 表示 $X_{j+1}\sim X_i$ 全部相等，其余相邻两项均不相等的方案数和 $X_{j}\sim X_i$ 全部相等，其余相邻两项均不相等的方案数的和。

于是

$$dp_i=\sum (-1)^{i-j}dp_j\min_{j<k\le i} A_k$$

其中的 $\min\limits_{j<k\le i} A_k$ 可以用单调栈维护。

实现

#include <bits/stdc++.h>

typedef long long int ll;
const int maxn = 5e5 + 19, mod = 998244353;

int n, a[maxn];
int st[maxn], top;
int dp[maxn], sum, s[maxn];

int main(){
    std::scanf("%d", &n);
    for(int i = 1; i <= n; ++i) std::scanf("%d", a + i);
    dp[0] = 1, s[1] = 1;
    for(int i = 1; i <= n; ++i){
        while(top && a[st[top]] >= a[i])
            sum = (sum - (ll)a[st[top]] * (s[st[top]] - s[st[top - 1]])) % mod, --top;
        st[++top] = i, sum = (sum + (ll)a[st[top]] * (s[st[top]] - s[st[top - 1]])) % mod;
        dp[i] = -sum, s[i + 1] = (s[i] + dp[i]) % mod;
    }
    if(n & 1) dp[n] = -dp[n];
    std::printf("%d\n", (dp[n] + mod) % mod);
}

来源

AtCoder Regular Contest 115 E - LEQ and NEQ

评论