A305 题解

思路

$k=1$

单调栈板子，设 $L_i,R_i$ 分别表示 $a_i$ 左边最靠近它比它小或相等的数的位置加一和右边最靠近它比它小的数的位置减一（方便判重），可以算出 $a_x$ 的贡献为：

$$a_x\sum_{l=L_x}^{x}\sum_{r=x}^{R_x}(r-l+1)$$

把这个式子拆开来：

$$a_x\bigg(\sum_{l=L_x}^{x}\sum_{r=x}^{R_x}(r+1)-\sum_{l=L_x}^{x}\sum_{r=x}^{R_x}l\bigg)$$$$a_x\bigg((x-L_x+1)\sum_{r=x}^{R_x}(r+1)-(R_x-x+1)\sum_{l=L_x}^{x}l\bigg)$$

然后预处理一下就行了。

$1 \le n,k \le 15$

记搜。

$1 \le n,k \le 10000$

首先，当 $k=1$ 时，答案即为：

$$\sum_{l=1}^{n}\sum_{r=l}^{n}\min(l,\dots ,r)\times(r-l+1)$$

考虑对于一个这样的区间 $[l,r]$，可以包含他的区间左右端点的范围是 $[1,l],[r,n]$，那么如果有多个区间包含呢？

我们注意到，对于多个区间包含一个区间，我们不用管多个区间的具体包含关系，只需要看端点位置的方案数。

考虑要在一个长为 $L$ 的区间内放 $t$ 个端点的方案数，可以直接插板法 $\binom{L+t-1}{t}$。

那么可以自然推出对于一个区间 $[l,r]$，要在外面放 $k-1$ 个区间，左右端点放置方案数为 $FL(l)=\binom{l+k-2}{k-1},FR(r)=\binom{n-r+k-1}{k-1}$。

则答案即为：

$$\sum_{l=1}^{n}\sum_{r=l}^{n}\min(l,\dots ,r)\times(r-l+1)\times FL(l)\times FR(r)$$

直接暴力枚举即可，时间复杂度 $O(n^2)$。

$1 \le n,k \le 10^5$

先单调栈优化一下：

$$a_x\sum_{l=L_x}^{x}\sum_{r=x}^{R_x}(r-l+1)\times FL(l)\times FR(r)$$

然后把式子拆开：

$$a_x\Bigg[\bigg(\sum_{l=L_x}^{x}\sum_{r=x}^{R_x}(r+1)\times FL(l)\times FR(r)\bigg)-\bigg(\sum_{l=L_x}^{x}\sum_{r=x}^{R_x}l\times FL(l)\times FR(r)\bigg)\Bigg]$$

继续拆：

$$a_x\Bigg[\bigg(\sum_{l=L_x}^{x}FL(l)\bigg)\times\bigg(\sum_{r=x}^{R_x}(r+1)\times FR(r)\bigg)-\bigg(\sum_{r=x}^{R_x}FR(r)\bigg)\times\bigg(\sum_{l=L_x}^{x}l\times FL(l)\bigg)\Bigg]$$

然后就可以前缀和优化了。

设：

$$totl_l=\sum_{i=1}^{l}FL(i),totls_l=\sum_{i=1}^{l}\Big(i\times FL(i)\Big)$$$$totr_r=\sum_{i=1}^{r}FR(i),totrs_r=\sum_{i=1}^{r}\Big((i+1)\times FR(i)\Big)$$

然后设：

$$suml=totl_x-totl_{L_x-1},sumls=totls_x-totls_{L_x-1}$$$$sumr=totr_{R_x}-totr_{x-1},sumrs=totrs_{R_x}-totrs_{x-1}$$

则原式即为：

$$a_x\Big(suml\times sumrs-sumr\times sumls\Big)$$

由于要预处理 $totl,totls,totr,totrs$，时间复杂度为 $O(n+k)$。

$1\le n \le 3\times10^6,1\le k \le 10^9$

注意到 $FL,FR$ 都可以表示为 $\binom{i+k-1}{i}$ 的形式。

$$FL(l)=\binom{(l-1)+k-1}{l-1},FR(r)=\binom{(n-r)+k-1}{n-r}$$

所以设 $g_i=\binom{i+k-1}{i}$。

经过观察，我们可以注意到 $g_{i}=\frac{(i+k-1)\times(i+k-2)\times\dots\times k}{1\times2\times\dots\times i}$，$g_{i-1}=\frac{(i+k-2)\times(i+k-3)\times\dots\times k}{1\times2\times\dots\times (i-1)}$，所以得出递推式 $g_i=g_{i-1}\times\frac{i+k-1}{i}$，其中 $i-1$ 的逆元不超过 $n$，可以 $O(n)$ 求出。

求出 $g_i$ 后就可以计算 $FL(l)=g_{l-1},FR(r)=g_{n-r}$ 了，然后求出 $totl,totls,totr,totrs$ 即可，时间复杂度 $O(n)$。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
int n,k,a[3000010];
int inv[3000010];//逆元数组 
int L[3000010],R[3000010];//单调栈求第i个数左边右边第一个比他小的数前一个数，即包含i且最小值为ai的区间 
int totl[3000010],totls[3000010],totr[3000010],totrs[3000010],g[3000010];//组合数预处理，具体意思可以看题解 
int stk[3000010],sti;//栈 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>k;k%=mod;
	inv[0]=inv[1]=1;
	for(int i=2;i<=n;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;//线性求逆元 
	for(int i=1;i<=n;i++)cin>>a[i];
	g[0]=1;
	for(int i=1;i<=n;i++){
		g[i]=1ll*g[i-1]*((i+k-1+mod)%mod)%mod*inv[i]%mod;//预处理g 
	} 
	for(int i=1;i<=n;i++){
		totl[i]=(totl[i-1]+g[i-1])%mod;
		totls[i]=(totls[i-1]+1ll*i*g[i-1]%mod)%mod;
		totr[i]=(totr[i-1]+g[n-i])%mod;
		totrs[i]=(totrs[i-1]+1ll*(i+1)*g[n-i]%mod)%mod;//预处理 
	}
	//单调栈求L,R 
	for(int i=1;i<=n;i++){
		while(sti&&a[i]<=a[stk[sti]])R[stk[sti--]]=i-1;
		stk[++sti]=i;
	}
	while(sti)R[stk[sti--]]=n;
	for(int i=n;i;i--){
		while(sti&&a[i]<a[stk[sti]])L[stk[sti--]]=i+1;
		stk[++sti]=i;
	}
	while(sti)L[stk[sti--]]=1;
	//统计答案 
	ll ans=0;
	for(int i=1;i<=n;i++){
		int suml=(totl[i]-totl[L[i]-1]+mod)%mod,sumls=(totls[i]-totls[L[i]-1]+mod)%mod,sumr=(totr[R[i]]-totr[i-1]+mod)%mod,sumrs=(totrs[R[i]]-totrs[i-1]+mod)%mod;
		ans=(ans+a[i]*((1ll*suml*sumrs%mod-1ll*sumls*sumr%mod+mod)%mod)%mod)%mod;
	}
	cout<<ans;
	return 0;
}