AtCoder Beginner Contest 276F - Double Chance

龙繁
2023-12-01

我摆烂了

平均数会吧?(小学芝士)

费马求逆元会吧?(OIer必备)

树状数组会吧?(树状数组你不会你打什么ABC?)

那这题你会了。(逃

题目大意

MYi不会翻译

给定一个长度为 N N N 的序列 A A A ,对于每个 K ( 1 ≤ K ≤ N ) K (1 \leq K \leq N) K(1KN),求:

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

给定数据

一共两行。

第一行是序列长度 N N N

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

输出要求

一共 N N N 行。

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

解题思路

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

什么意思呢,就是说,答案(还没 m o d   p mod \ p mod p )就等于所有 m a x ( A x , A y ) max( A_x,A_y) max(Ax,Ay) 的和除以方案数,即 k 2 k^2 k2

得到这个答案后,我们就按照题目说的求出这个 R R R 。求 R R R 的话直接给公式,证明过程我也不会。(逃
对于 m n ,可以快乐地得出  R = m × n p − 2   m o d   p 对于 \frac{m}{n} ,可以快乐地得出 \ R=m \times n^{p-2} \ mod \ p 对于nm,可以快乐地得出 R=m×np2 mod p
那么每个 A i A_i Ai 对第 k k k 个答案的贡献是多少呢?不要看我,看题。

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

嘶……

计数…求和……

哈,树状数组!

开一个树状数组维护有多少个小于等于 A i A_i Ai 的数:

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 A_i Ai 的数的和:

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

 类似资料:

相关阅读

相关文章

相关问答