CF1009E Intercity Travelling 题解

· · 题解

前言

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

正文

题目分析

由于一号点出发相当于一号点必须休息，那么只剩下了 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

#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;
}