昨晚 ABC F 题解

cjdst

2026-01-04 23:42:01

发布于：广东

48阅读

0回复

0点赞

简单数数题。要是最后 30min 没写作业说不定就过了。

题意解析：定义一个长度为 $n$ 的数组 $A$ 的“峰”与“谷”如下：

若 $2\le i\le n$ 且 $A_{i-1}\lt A_i\gt A_{i+1}$ ，则 $i$ 为 $A$ 的峰。
若 $2\le i\le n$ 且 $A_{i-1}\gt A_i\lt A_{i+1}$ ，则 $i$ 为 $A$ 的谷。

定义一个数组 $A$ 为山峰数组当且仅当它的峰的数量严格大于谷的数量。

给定一个 $n$ 的排列 $A$ ，求 $A$ 有多少个子序列为山峰数组。

我们考虑什么情况下才是山峰数组。

注意到不算两边的话，一定是“...峰谷峰谷峰谷...”状的。

再进一步，分类讨论一下，可以发现一个长度为 $k$ 的数组 $B$ 是山峰数组当且仅当 $B_1\lt B_2$ 且 $B_{n-1}\gt B_n$ 。

现在问题就简单了。

先考虑暴力。

我们可以暴力枚举 $i\lt j\le k\lt l$ 分别作为子数组的 $B_1,B_2,B_{k-1},B_k$ ，如果 $A_i\lt A_j$ 且 $A_k\gt A_l$ ，则不论中间是啥，都可以构成山峰数组，对答案的贡献为 $\max\{2^{k-j-1},1\}$ （因为 $j=k$ 时前面的是 $\frac{1}{2}$ 所以要对 $1$ 取最大值）。这样是 $O(n^4)$ 的。

然后推式子。

$\sum_{i=1}^n\sum_{j=i+1}^n\sum_{k=j}^n\sum_{l=k+1}^n [A_i\lt A_j][A_k\gt A_l]\max\{2^{k-j-1},1\}\\ =\sum_{i=1}^n\sum_{j=i+1}^n[A_i\lt A_j]\sum_{k=j}^n\sum_{l=k+1}^n [A_k\gt A_l]\max\{2^{k-j-1},1\}\\ =\sum_{j=2}^{n-1}\sum_{k=j}^n(\sum_{i=1}^{j-1}[A_i\lt A_j])(\sum_{l=k+1}^n [A_l\lt A_k])\max\{2^{k-j-1},1\}\\$

显然我们可以通过树状数组 $O(n\log n)$ 预处理出 $\sum_{j=1}^{i-1} [A_j\lt A_i]$ 与 $\sum_{j=i+1}^{n} [A_j\lt A_i]$ ，分别记作 $\text{pre}_i,\text{suf}_i$ 。则原式为：

$\sum_{i=2}^{n-1}\sum_{j=i}^n\text{pre}_i\text{suf}_j\max\{2^{j-i-1},1\}\\$

$\max$ 有点难搞，拆开吧。

$\sum_{i=2}^{n-1}\text{pre}_i\text{suf}_i+\sum_{i=2}^{n-1}\sum_{j=i+1}^n\text{pre}_i\text{suf}_j2^{j-i-1}\\$

然后继续转化。注意到 $2$ 的整数次幂是可逆的。所以：

$\sum_{i=2}^{n-1}\text{pre}_i\text{suf}_i+\sum_{i=2}^{n-1}\sum_{j=i+1}^n\text{pre}_i\text{suf}_j2^{j-i-1}\\ =\sum_{i=2}^{n-1}\text{pre}_i\text{suf}_i+\sum_{i=2}^{n-1}\sum_{j=i+1}^n\text{pre}_i\text{suf}_j\frac{2^j}{2^{i+1}}\\ =\sum_{i=2}^{n-1}\text{pre}_i\text{suf}_i+\sum_{i=2}^{n-1}\frac{\text{pre}_i}{{2^{i+1}}}\sum_{j=i+1}^n\text{suf}_j2^j\\$

我们只需要递推求出 $\sum_{j=i+1}^n\text{suf}_j2^j$ 即可。

代码如下：

namespace cjdst{
    const ll mod = 998244353;
	const ll inv2 = mod / 2 + 1;
    ll ksm[600005], invksm[600005];

	void init(){
		ksm[0] = invksm[0] = 1;
		for(int i = 1; i <= 600000; i++){
			ksm[i] = ksm[i - 1] * 2 % mod;
			invksm[i] = invksm[i - 1] * inv2 % mod;
		}
	}

	void solve(){
		int n;
		std::cin >> n;
		std::vector <int> a(n + 5);
		for(int i = 1; i <= n; i++){
			std::cin >> a[i];
		}
		Fenwick_Tree <ll> tr1(n + 5), tr2(n + 5);
		std::vector <ll> b(n + 5), c(n + 5), d(n + 5);
		for(int i = 1; i <= n; i++){
			tr2.modify(a[i], 1);
		}
		for(int i = 1; i <= n; i++){
			tr2.modify(a[i], -1);
			b[i] = tr1.query(a[i] - 1);
			c[i] = tr2.query(a[i] - 1);
			tr1.modify(a[i], 1);
		}
		for(int i = n; i; i--){
			d[i] = d[i + 1] + c[i] * ksm[i];
			d[i] %= mod;
		}
		ll ans = 0;
		for(int i = 2; i < n; i++){
			ans += b[i] * c[i] % mod;
			ans %= mod;
		}
		for(int i = 1; i <= n; i++){
			ans += b[i] * d[i + 1] % mod * invksm[i + 1] % mod;
			ans %= mod;
		}
		std::cout << ans << '\n';
	}
}

时间复杂度： $O(n\log n)$ 。

有帮助，赞一个

去预览

0/2000

全部评论 3

咕咕咕
%%%

2026-01-05 来自江西
1
cjdst
没啥用的 trick：注意到对于任意奇数 $k$ ， $2\times \frac{k+1}{2}=k+1$ ，所以 $\frac{k+1}{2}$ 是 $2$ 在模 $k$ 意义下的乘法逆元

2026-01-04 来自广东
0
cjdst
d

2026-01-04 来自广东
0

全部评论 3

热门讨论