比较自然的容斥 + DP。
$b_i\neq b_{i+1}$ 不好做。于是考虑容斥，求至少有 $k$ 对 $b_i=b_{i+1}$ 的方案数。最终答案为：
$a_i$ 值域很大，一位一位地做是没有前途的。注意到有 $k$ 对相等的数会形成 $n-k$ 个连续段。考虑对此计数，设 $f(i,j)$ 表示当前位置为 $i$，形成至多 $k$ 个连续段的方案数，得到朴素的状态转移方程。
由于容斥系数，所以说只需要记录 $j$ 的奇偶即可，转移不变，时间复杂度为 $\mathcal O(n^2)$。
尝试优化转移 。考虑新加入的 $a_i$ 有何贡献。设上一个比它小的数为 $a_p$。容易发现对于 $p< k\le i$ 的贡献为 $a_i$。对于 $1\le k\le p$，位置 $i$ 与位置 $p$ 贡献相同，继承即可。
$p$ 由单调栈求出。前缀和辅助转移即可。时间复杂度 $\mathcal O(n)$。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| #include<iostream>
#include<cstdio>
using namespace std;
const int N=5e5+10,mod=998244353;
template<class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
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+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n;
int a[N];
int top,sta[N];
int f[N][2];
inline int adj(int x){return (x>=mod)?x-mod:x;}
int main()
{
read(n);
for(int i=1;i<=n;i++)read(a[i]);
f[0][0]=1;
for(int i=1;i<=n;i++)
{
while(top&&a[sta[top]]>=a[i])top--;
int j=sta[top];
if(!j)
{
f[i][0]=1ll*a[i]*(f[i-1][1])%mod;
f[i][1]=1ll*a[i]*(f[i-1][0])%mod;
}
else
{
f[i][0]=adj(adj(f[j][0]-f[j-1][0]+mod)+1ll*a[i]*adj(f[i-1][1]-f[j-1][1]+mod)%mod);
f[i][1]=adj(adj(f[j][1]-f[j-1][1]+mod)+1ll*a[i]*adj(f[i-1][0]-f[j-1][0]+mod)%mod);
}
f[i][0]=adj(f[i][0]+f[i-1][0]);
f[i][1]=adj(f[i][1]+f[i-1][1]);
sta[++top]=i;
}
int ans0=adj(f[n][0]-f[n-1][0]+mod),ans1=adj(f[n][1]-f[n-1][1]+mod);
printf("%d",(n&1)?adj(ans1-ans0+mod):adj(ans0-ans1+mod));
return 0;
}
|