AtCoder Beginner Contest 276F - Double Chance

我摆烂了

平均数会吧？（小学芝士）

费马求逆元会吧？（OIer必背备）

树状数组会吧？（树状数组你不会你打什么ABC？）

那这题你会了。（逃

题目大意

MYi不会翻译

给定一个长度为 $N$ 的序列 $A$ ，对于每个$K(1\le K\le N)$，求：

1. 从 $A$ 的前 $K$ 个数中选出一个数 $A_x$ ，再将其放回 $A$；
2. 重复第一步，设取出的数为 $A_y$ ；（ $x$ 可以等于 $y$ ）
3. 求 $\text{m}ax(A_x,A_y)$ 的数学期望 $modp$ 的值。 $mod$ 前面那些东西可能是一个分数，对于任意一个分数 $\frac{m}{n}$ ，我们可以得到一个数 $R$ ，使得 $R\times n\equiv m(modp)$ ，其中 $p=998244353$ ，你需要输出这个 $R$ 。

给定数据

一共两行。

第一行是序列长度 $N$ 。

第二行是给定的序列 $A$ 。

输出要求

一共 $N$ 行。

第 $k$ 行表示对于前 $k$ 个数的答案。

解题思路

首先说一句，这里并不需要什么神奇的高中数学知识，我们只需要知道一件事，那就是数学期望说白了就是平均数。

什么意思呢，就是说，答案（还没 $modp$ ）就等于所有 $max(A_x,A_y)$ 的和除以方案数，即 $k^2$ 。

得到这个答案后，我们就按照题目说的求出这个 $R$ 。求 $R$ 的话直接给公式，证明过程我也不会。（逃
$$对于\frac{m}{n}，可以快乐地得出R=m\times n^{p-2}modp$$
那么每个 $A_i$ 对第 $k$ 个答案的贡献是多少呢？不要看我，看题。

它和比它小的的数取较大值得到的是它本身，还取了两次；如果1、2步选两次 $A_i$ 得到的还是它本身；它和所有比它大的数取较大值得到的是那些比它大的数，即所有比它大的数之和，同样取了两次。

嘶……

计数…求和……

哈，树状数组！

开一个树状数组维护有多少个小于等于 $A_i$ 的数：

ll query1(ll x){
	ll sum=0;
	while(x){
		sum+=tr1[x];
		x-=lowbit(x);
	}
	return sum%mod;
}
void updt1(ll x){
	while(x<=N){
		++tr1[x];
		x+=lowbit(x);
	}
}

再开一个树状数组维护小于等于 $A_i$ 的数的和：

ll query2(ll x){
	ll sum=0;
	while(x){
		sum=(sum+tr2[x])%mod;
		x-=lowbit(x);
	}
	return sum%mod;
}
void updt2(ll x,ll num){
	while(x<=N){
		tr2[x]=(tr2[x]+num)%mod;
		x+=lowbit(x);
	}
}

按照上面说的方法去处理：

ll pos=query1(a[i]),tmps=(query2(200000)-query2(a[i])+mod)%mod;
g=(g+2*pos*a[i]%mod+a[i]+2*tmps)%mod;
t=i*i%mod;
printf("%lld\n",g*ksm(t,mod-2)%mod);

最后更新一下树状数组：

updt1(a[i]);
updt2(a[i],a[i]);

然后就可以快乐地开摆了。

yee.jpg

AC Code

#include<bits/stdc++.h>
#define pii pair<ll,ll>
#define ll long long
#define F first
#define S second
using namespace std;
const int mod=998244353,N=2e5+5;
ll ksm(ll a,ll b){
	if(b==0) return 1ll;
	ll tmp=ksm(a,b>>1ll);
	if(b&1) return tmp*tmp%mod*a%mod;
	else return tmp*tmp%mod;
}
ll n,a[N],tr1[N],tr2[N],g,t;
ll lowbit(ll x){
	return x&(-x);
}
ll query1(ll x){
	ll sum=0;
	while(x){
		sum+=tr1[x];
		x-=lowbit(x);
	}
	return sum%mod;
}
ll query2(ll x){
	ll sum=0;
	while(x){
		sum=(sum+tr2[x])%mod;
		x-=lowbit(x);
	}
	return sum%mod;
}
void updt1(ll x){
	while(x<=N){
		++tr1[x];
		x+=lowbit(x);
	}
}
void updt2(ll x,ll num){
	while(x<=N){
		tr2[x]=(tr2[x]+num)%mod;
		x+=lowbit(x);
	}
}
int main(){
	scanf("%d",&n);
	for(ll i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	printf("%lld\n",a[1]);
	updt1(a[1]);
	updt2(a[1],a[1]);
	g=a[1];
	for(ll i=2;i<=n;++i){
		ll pos=query1(a[i]),tmps=(query2(200000)-query2(a[i])+mod)%mod;
		g=(g+2*pos*a[i]%mod+a[i]+2*tmps)%mod;
		t=i*i%mod;
		printf("%lld\n",g*ksm(t,mod-2)%mod);
		updt1(a[i]);
		updt2(a[i],a[i]);
	}
	return 0;
}

彩蛋

你猜为什么输出结果时要用莫名其妙的g和t？