简单数数题。要是最后 30min 没写作业说不定就过了。
题意解析：定义一个长度为 n 的数组 A 的“峰”与“谷”如下：
- 若 2≤i≤n 且 Ai−1<Ai>Ai+1，则 i 为 A 的峰。
- 若 2≤i≤n 且 Ai−1>Ai<Ai+1，则 i 为 A 的谷。
定义一个数组 A 为山峰数组当且仅当它的峰的数量严格大于谷的数量。
给定一个 n 的排列 A，求 A 有多少个子序列为山峰数组。
我们考虑什么情况下才是山峰数组。
注意到不算两边的话，一定是“...峰谷峰谷峰谷...”状的。
再进一步，分类讨论一下，可以发现一个长度为 k 的数组 B 是山峰数组当且仅当 B1<B2 且 Bn−1>Bn。
现在问题就简单了。
先考虑暴力。
我们可以暴力枚举 i<j≤k<l 分别作为子数组的 B1,B2,Bk−1,Bk，如果 Ai<Aj 且 Ak>Al，则不论中间是啥，都可以构成山峰数组，对答案的贡献为 max{2k−j−1,1}（因为 j=k 时前面的是 21 所以要对 1 取最大值）。这样是 O(n4) 的。
然后推式子。
i=1∑nj=i+1∑nk=j∑nl=k+1∑n[Ai<Aj][Ak>Al]max{2k−j−1,1}=i=1∑nj=i+1∑n[Ai<Aj]k=j∑nl=k+1∑n[Ak>Al]max{2k−j−1,1}=j=2∑n−1k=j∑n(i=1∑j−1[Ai<Aj])(l=k+1∑n[Al<Ak])max{2k−j−1,1}
显然我们可以通过树状数组 O(nlogn) 预处理出 ∑j=1i−1[Aj<Ai] 与 ∑j=i+1n[Aj<Ai]，分别记作 prei,sufi。则原式为：
i=2∑n−1j=i∑npreisufjmax{2j−i−1,1}
max 有点难搞，拆开吧。
i=2∑n−1preisufi+i=2∑n−1j=i+1∑npreisufj2j−i−1
然后继续转化。注意到 2 的整数次幂是可逆的。所以：
i=2∑n−1preisufi+i=2∑n−1j=i+1∑npreisufj2j−i−1=i=2∑n−1preisufi+i=2∑n−1j=i+1∑npreisufj2i+12j=i=2∑n−1preisufi+i=2∑n−12i+1preij=i+1∑nsufj2j
我们只需要递推求出 ∑j=i+1nsufj2j 即可。
代码如下：
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(nlogn)。
有帮助，赞一个