做集团网站的,百度学术官网论文查重免费,建设视频网站,微信推广多少钱一次正题
题目链接:https://www.luogu.com.cn/problem/P3352 题目大意 nnn个数字的一个序列#xff0c;每次随机选择一个区间让这个区间所有数等于这个区间的最大值#xff0c;重复qqq次#xff0c;对每个位置求所有情况下这个位置的值的和。 1≤n,q≤4001\leq n,q\leq 4001≤n…正题
题目链接:https://www.luogu.com.cn/problem/P3352 题目大意
nnn个数字的一个序列每次随机选择一个区间让这个区间所有数等于这个区间的最大值重复qqq次对每个位置求所有情况下这个位置的值的和。
1≤n,q≤4001\leq n,q\leq 4001≤n,q≤400保证数据随机 解题思路
设fk,l,rf_{k,l,r}fk,l,r表示使用了kkk次目前覆盖了极大区间l,rl,rl,r时的方案。
这个极大区间就是无法继续向左右扩展就是左右两边是边界或者比这个区间内所有数都大不然相同的方案会统计入不同的数组导致算重。
然后每次我们找一个数字开始向左右扩展到极大区间进行dpdpdp然后dpdpdp方程是 fk,l,rfk−1,l,r×gl,r∑iLl−1fk−1,i,r∑ir1Rfk−1,l,i1f_{k,l,r}f_{k-1,l,r}\times g_{l,r}\sum_{iL}^{l-1}f_{k-1,i,r}\sum_{ir1}^{R}f_{k-1,l,i1}fk,l,rfk−1,l,r×gl,riL∑l−1fk−1,i,rir1∑Rfk−1,l,i1 也就是固定端点的情况下扩展极大区间因为是反过来的所以这样是对的。
然后记录一个dpdpdp数组ansi,jans_{i,j}ansi,j表示数字iii至少为第jjj小的情况数这个每次dpdpdp后都可以统计。
上面每个dpdpdp区间相当于笛卡尔树上的区间因为数据随机所以每个位置只会计算logloglog次。
时间复杂度O(nq2n3)O(nq^2n^3)O(nq2n3) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N410,P1e97;
ll n,q,a[N],b[N],rk[N],f[2][N][N],ans[N][N],cnt[N];
void solve(ll x,ll L,ll R){for(ll iL;iR;i)for(ll ji;jR;j)f[0][i][j]f[1][i][j]0;f[0][L][R]1;for(ll k1;kq;k){for(ll iL;iR;i)for(ll ji;jR;j)f[k1][i][j]f[~k1][i][j]*(cnt[j-i1]cnt[i-1]cnt[n-j]);for(ll iL;iR;i){ll buf0;for(ll jR;ji;j--){(f[k1][i][j]buf)%P;(buff[~k1][i][j]*(n-j))%P;}}for(ll jL;jR;j){ll buf0;for(ll iL;ij;i){(f[k1][i][j]buf)%P;(buff[~k1][i][j]*(i-1))%P;}}}for(ll iL;iR;i){ll buf0;for(ll jR;ji;j--){(buff[q1][i][j])%P;(ans[j][rk[x]]buf)%P;}}return;
}
signed main()
{scanf(%lld%lld,n,q);for(ll i1;in;i)cnt[i]i*(i1)/2; for(ll i1;in;i){scanf(%lld,a[i]);b[i]a[i];}sort(b1,b1n);ll munique(b1,b1n)-b-1;for(ll i1;in;i)rk[i]lower_bound(b1,b1m,a[i])-b;for(ll i1;in;i){ll Li,Ri;while(L1a[L-1]a[i])L--;while(Rna[R1]a[i])R;solve(i,L,R);}for(ll i1;in;i){ll sum0;for(ll j1;jn;j){if(!ans[i][j]){continue;}for(ll k1;kj;k)(ans[i][j]P-ans[i][k])%P;(sumans[i][j]*b[j]%P)%P;}printf(%lld ,sum);}return 0;
}
