Intercity Travelling(数学公式推导 cf div2 E)

编程入门 行业动态 更新时间:2024-10-17 05:02:00

Intercity Travelling(<a href=https://www.elefans.com/category/jswz/34/1764151.html style=数学公式推导 cf div2 E)"/>

Intercity Travelling(数学公式推导 cf div2 E)

 

题目传送门:E. Intercity Travelling

 

题意:数轴上从0出发到n,值为1 - (n-1)的点中均可以休息,也可以不休息。现在给定一个数组a[ ],a[i]表示走长度为i的距离的困难度(保证a[i+1]>a[i]),设每种情况出现的可能性均相同,求所有可能性的期望困难度之和p*2^(n-1)。

 

思路:有题意可知,总共有2^(n-1)种情况。分别统计所有情况中a[i](1<=i<=n)出现的次数time[i],则所有可能性的期望困难度之和p=()/(2^(n-1)),所以答案ans= 。

 

下面是time[i]的推导:

 

数轴: 0  1  3  4  ...  n-2  n-1  n

 

time[1]:

所有情况从0 -> 1都需要a[1]  =>  需要 2^(n-1) 次

若1 -> 2需要a[1],则1必须休息,其余各点均无所谓  =>  需要2^(n-2)

若2 -> 3需要a[1],则2必须休息,其余各点均无所谓  =>  需要2^(n-2)

若3 -> 4需要a[1],则3必须休息,其余各点均无所谓  =>  需要2^(n-2)

......

若(n-1) -> n需要a[1],则n-1必须休息,其余各点均无所谓  =>  需要2^(n-2)

=> time[1]=2^(n-1)+(n-1)*2^(n-2)

 

tips: 这么算会不会有重复情况?可以看到算1-2时考虑过全为休息的情况,算2-3时又考虑了全为休息的情况。但实际这不是重复的,因为全为休息的情况本来就会在1-2、 2-3、 ...  (n-1)-n 时都产生一个a[1]的困难度。其他情况同理。

 

time[2]:

若0 -> 2需要a[2],则1必须不休息,其余各点均无所谓 => 需要2^(n-2)

若1 -> 3需要a[2],则1必须休息,2必须不休息,其余各点均无所谓 => 需要2^(n-3)

若2 -> 4需要a[2],则2必须休息,3必须不休息,其余各点均无所谓 => 需要2^(n-3)

若3 -> 5需要a[2],则3必须休息,4必须不休息,其余各点均无所谓 => 需要2^(n-3)

......

若(n-2) -> n需要a[2],则n-2必须休息,n-1必须不休息,其余各点均无所谓 => 需要2^(n-3)

=> time[2]=2^(n-2)+(n-2)*2^(n-3)

 

同理:

time[3]=2^(n-3)+(n-3)*2^(n-4)

time[4]=2^(n-4)+(n-4)*2^(n-5)

......

 

=> time[i] = 2^(n-i) + (n-i)*2^(n-i-1)   (其中1<=i<=n)

 

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;typedef long long ll;const int MAX =1e6+100;
const int mod=998244353;int n;
ll a[MAX];
ll x[MAX]; //x[i]表示2^iint main()
{scanf("%d",&n);x[0]=1;for(int i=1;i<=n;i++){x[i]=(x[i-1]*2)%mod;}ll ans=0;for(int i=1;i<=n;i++){scanf("%lld",&a[i]);ll time=(x[n-i]+(x[n-i-1]*(n-i))%mod)%mod;ans=(ans+(a[i]*time)%mod)%mod;}printf("%lld\n",ans);return 0;
}

 

更多推荐

Intercity Travelling(数学公式推导 cf div2 E)

本文发布于:2024-02-11 19:34:30,感谢您对本站的认可!
本文链接:https://www.elefans.com/category/jswz/34/1682961.html
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。
本文标签:数学公式   Travelling   Intercity   cf

发布评论

评论列表 (有 0 条评论)
草根站长

>www.elefans.com

编程频道|电子爱好者 - 技术资讯及电子产品介绍!