CF1591F Non-equal Neighbours （容斥qwq）

容斥神仙题 qwq。

题意

给定一个长度为 \(n\) 的序列 \(a_1,a_2,\cdots ,a_n\)，输出满足如下条件的序列 \(x\) 的方案数：

1. \(1\leq x_i\leq a_i\)
2. \(x_i\neq x_{i+1}(1\leq i\leq n-1)\)

• \(2\le n\le 5\times 10^5,1\le a_i\le 10^9\)

Solution

首先我们规定形如 \(x_{i} = x_{i + 1}\) 的点为坏点。

令 \(f_{i}\) 表示至少有 \(i\) 个坏点的方案数，那么套上容斥的式子：

那么我们令所有的坏点向左合并，即 $x_i \gets x_i,x_{i + 1} $ 其中 \(x_i = x_{i + 1}\)，假设有 \(k\) 个坏点，那么恰好减少 \(k\) 个数，而这等价于将序列划分成 \(n – k\) 段，每段内都是相同的数。

注意这里只是强制限定了每一段内相同，不代表相邻段之间必须不同，因为我们是至少。

所以我们考虑用 dp 求出这样划分的方案数，令 \(dp[i][j]\) 表示填了 \(i\) 个数，划分出 \(j\) 段的方案数。

那么对答案进行改写：

先考虑朴素转移：

代表添加一段 \((k + 1,i)\) 的线段，有 \(\min_{o = k + 1}^{i}a_o\) 种填法。

复杂度还不够优秀。

我们发现最后只关心划分出的段数的奇偶，所以可以直接改写成 \(dp[i][0/1]\) 代表划分成 偶数/奇数 段的方案数。

方程又变成了：

那么前面那个东西可以前缀和优化。

后面那一坨，我们维护单调栈，找到左边第一个小于 \(a[i]\) 的。

• 如果不存在这样的，那么 \(a[i]\) 就是最小值，直接前缀和乘上即可。
• 否则考虑令前面的位置为 \(p\) ，则 \([p + 1…i,i]\) 这些区间都是以 \(a[i]\) 为最小值的。也就是说你可以从 \(dp[p…i – 1]\) 转移过来，因为我们的转移相当于在这个位置后面插入一段。在这之前的最小值都和 \(a[i]\) 没关系！！所以直接继承 \(dp[p][op]\) 就是贡献，因为这个玩意就等价于前面的 $\sum dp[k][op \text{ xor } 1] \times \min $。

最后根据 \(n\) 的奇偶性，我们可以得出 \(dp[n][0/1]\) 对应的奇偶性，也就是 \(n – 2\times k\) 和 \(n – (2\times k + 1)\) 的奇偶性，用偶的减去奇的即可。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i<(b);++i)
#define rrep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
template <typename T>
inline void read(T &x){
    x=0;char ch=getchar();bool f=0;
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=-x;
}
template <typename T,typename ...Args>
inline void read(T &tmp,Args &...tmps){read(tmp);read(tmps...);}
const int N = 5e5 + 5;
const int mod = 998244353;
inline void add(int &x,int y){
    if((x += y) >= mod)x -= mod;
}
vector<int>S;
int dp[N][2],s[N][2];
int a[N],n;
signed main(){
    read(n);
    rep(i,1,n)read(a[i]);
    dp[0][0] = s[0][0] = 1;
    rep(i,1,n){
        while(!S.empty() && a[S.back()] >= a[i])S.pop_back();
        if(S.empty()){
            for(int x : {0,1})dp[i][x] = 1ll * s[i - 1][x ^ 1] * a[i] % mod;
        }
        else{
            for(int x : {0,1})dp[i][x] = (dp[S.back()][x] + 1ll * (s[i - 1][x ^ 1] - s[S.back() - 1][x ^ 1] + mod) * a[i] % mod) % mod;
        }
        S.push_back(i);
        s[i][0] = (s[i - 1][0] + dp[i][0]) % mod;
        s[i][1] = (s[i - 1][1] + dp[i][1]) % mod;
    }
    int ans = (dp[n][0] - dp[n][1] + mod) % mod;
    if(n & 1)ans = 1ll * ans * (mod - 1) % mod;
    printf("%d",ans);
}

都看到这了留个赞呗qwq。

原文地址：http://www.cnblogs.com/wsxxs/p/16922613.html