深圳网站设计公司费用多少,南宁百度关键词优化,惠州网络推广费用,删除自豪地采用wordpress正题
题目链接:https://www.luogu.com.cn/problem/P6046 题目大意 nnn个数#xff0c;每次选择两个相邻的数删除小的那个#xff0c;求每个数期望存活轮数。 解题思路
相当于一条链每次缩掉一条边#xff0c;我们发现其实每个点只需要考虑左右第一个比它大的就好了。定义…正题
题目链接:https://www.luogu.com.cn/problem/P6046 题目大意
nnn个数每次选择两个相邻的数删除小的那个求每个数期望存活轮数。 解题思路
相当于一条链每次缩掉一条边我们发现其实每个点只需要考虑左右第一个比它大的就好了。定义P(x)P(x)P(x)表示xxx轮攻击后还没有死亡的概率有ans∑i1n−1P(i)ans\sum_{i1}^{n-1}P(i)ansi1∑n−1P(i)
对于每个P(i)P(i)P(i)我们固定到左边第一个比它大的数的路径然后剩下的随便选就可以用组合数来计算方案而左右两边都减去后要容斥加上两边都被删除的方案数。
时间复杂度O(n2logP)O(n^2\log P)O(n2logP) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll XJQ998244353,N60;
ll n,a[N],fac[N],inv[N],ans;
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%XJQ;xx*x%XJQ;b1;}return ans;
}
ll C(ll x,ll y)
{if(x0||y0||xy)return 0;return fac[x]*inv[y]%XJQ*inv[x-y]%XJQ;
}
int main()
{scanf(%lld,n);a[0]a[n1]2147483647;fac[0]inv[0]1;for(ll i1;in;i){scanf(%lld,a[i]);fac[i]fac[i-1]*i%XJQ;inv[i]inv[i-1]*power(i,XJQ-2)%XJQ;}for(ll p1;pn;p){ll lp-1,rp1;ans0;while(a[l]a[p])l--;while(a[r]a[p])r;for(ll i1;in;i){ll tmp0,d1p-l,d2r-p;if(l)tmp(tmpC(n-1-d1,i-d1))%XJQ;if(r!n1)tmp(tmpC(n-1-d2,i-d2))%XJQ;if(r!n1l)tmp(tmp-C(n-1-d1-d2,i-d1-d2)XJQ)%XJQ;ans(ans1-tmp*power(C(n-1,i),XJQ-2)%XJQXJQ)%XJQ;}printf(%lld ,ans);}
}
