CF1009E Intercity Travelling 题解

Zi_Gao

2023 年 11 月 10 日

614 次浏览

1 条评论

889字数

题解

## 前言

这种推式子的题只给结论？~~有没有素质~~

## 正文

### 题目分析

由于一号点出发相当于一号点必须休息，那么只剩下了 $n-1$ 个点，总的选择方案是 $2_{n-1}$，而题目要求答案乘上 $2_{n-1}$ 相当于消掉了，只需要统计每种方案的代价和即可。

经典套路分开讨论每个 $a_i$ 的贡献。对于每个 $a_i$ 同样进行拆分，考虑这个 $a_i$ 在哪个位置会造成贡献，既然能产生 $a_i$ 的贡献，说明前面一定是 $a_1,a_2,\cdots,a_{i-1}$ 那么相当于固定了 $i$ 长度序列不能动，中间不能休息，并且只有这个要求，其他地方随便选，休息不休息都可以。但是对于一号点要钦定必须休息所以需要分开讨论一下，设选择作为 $a_i$ 的这个点位置在 $pos$：

1. 当 $pos=i$ 时，满足两个条件，剩下随便选，答案为 $2^{n-i}$，并且这种情况会出现一次。
2. 其他情况，需要满足一号点必须休息，并且固定了长度为 $i$ 只有 $n-i-1$ 个地方随便选了，答案为 $2^{n-i-1}$，并且这种情况会出现 $n-i$ 次。

那么总的答案为：

$$
ans=\sum_{i=1}^{n}\left(2^{n-i}+\left(n-i\right)\times2^{n-i-1}\right)\times a_i
$$

### 代码实现

注意 $n-i-1$ 可能为负数，但是并不需要逆元因为这时 $n-i$ 为 $0$。

AC CODE

```cpp
#include<bits/stdc++.h>
// #define ONLINE_JUDGE
#define INPUT_DATA_TYPE int
#define OUTPUT_DATA_TYPE long long
INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){if(x<0)x=-x,putchar('-');if(x>9)print(x/10);putchar(x%10^48);return;}

long long p[1000010];

int main(){
	#ifndef ONLINE_JUDGE
	freopen("name.in", "r", stdin);
	freopen("name.out", "w", stdout);
	#endif

register int i,n=read();
    const long long mod=998244353;
    register long long ans=0;
    p[0]=1;
    for(i=1;i<=n;++i) p[i]=(p[i-1]<<1)%mod;
    for(i=1;i<=n;++i)
        (ans+=(p[n-i]+((n-i-1)>=0?(p[n-i-1]*(n-i)):0))%mod*read())%=mod;

print(ans);

#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	#endif
    return 0;
}
```

最后修改：2023 年 11 月 10 日