E. Intercity Travelling(组合数)

组合数)"/>

E. Intercity Travelling(组合数)

• E. Intercity Travelling

题意

给出一个n，n个困难值，长度为n的直线距离，然后每个点可以休息，一旦休息困难值将从1开始。问困难值的期望*2^n-1

思路:

一共有2^n-1种情况，乘以期望，其实就是这么多种情况，每种情况的困难值的和
就可以分别计算每个位置的值被用了多少次
Ni表示a[i]被用的次数 N 1 = ∑ i = 0 n − 1 ( i + 1 ) ∗ C n − 1 i N1=\sum_{i=0}^{n-1}(i+1)*C_{n-1}^{i} N1=i=0∑n−1​(i+1)∗Cn−1i​
N 1 = 1 ∗ C n − 1 0 + 2 ∗ C n − 1 1 + 3 ∗ C n − 1 2 . . . . + n ∗ C n − 1 n − 1 N1=1*C_{n-1}^{0}+2*C_{n-1}^{1}+3*C_{n-1}^{2}....+n*C_{n-1}^{n-1} N1=1∗Cn−10​+2∗Cn−11​+3∗Cn−12​....+n∗Cn−1n−1​
C n − 1 i = C n − 1 n − 1 − i C_{n-1}^{i}=C_{n-1}^{n-1-i} Cn−1i​=Cn−1n−1−i​
N 1 = 1 ∗ C n − 1 n − 1 + 2 ∗ C n − 1 n − 2 + 3 ∗ C n − 1 n − 3 . . . . + n ∗ C n − 1 0 N1=1*C_{n-1}^{n-1}+2*C_{n-1}^{n-2}+3*C_{n-1}^{n-3}....+n*C_{n-1}^{0} N1=1∗Cn−1n−1​+2∗Cn−1n−2​+3∗Cn−1n−3​....+n∗Cn−10​
2 N 1 = （ n + 1 ） ∗ ∑ i = 0 n − 1 C n − 1 i = ( n + 1 ) ∗ 2 n − 1 2N1=（n+1）*\sum_{i=0}^{n-1}C_{n-1}^{i}=(n+1)*2^{n-1} 2N1=（n+1）∗i=0∑n−1​Cn−1i​=(n+1)∗2n−1
N 1 = ( n + 1 ) ∗ 2 n − 2 N1=(n+1)*2^{n-2} N1=(n+1)∗2n−2

那么N2就可以由N1递推出来，出现如果出现a[1]的后面一个点不休息，那么就会出现a[2]，总共有n-1个点，其中紧靠着出现a[1]的一个点始终为0，实际上可计算的就变成n-2个点了，因此N2相当于将n用n-1代入N1就得到公式了
N 2 = ( n ) ∗ 2 n − 3 N2=(n)*2^{n-3} N2=(n)∗2n−3
那么
N i = ( n + 2 − i ) ∗ 2 n − 1 − i Ni=(n+2-i)*2^{n-1-i} Ni=(n+2−i)∗2n−1−i
最终的答案
a n s = ∑ i = 1 n N i ∗ a [ i ] ans=\sum_{i=1}^{n}Ni*a[i] ans=i=1∑n​Ni∗a[i]

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
typedef vector<int>vi;#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define fi first
#define se second
#define de(x) cout<<#x<<"="<<x<<endl;
#define dd(x) cout<<#x<<"="<<x<<" " ;
#define pb(x) push_back(x)
#define per(i,a,b) for(int i=(b)-1;i>=(a);--i)
const int N=1e6+5;
const ll mod=998244353;
ll a[N];
ll mod_pow(ll x,ll n){if(n==-1)return mod_pow(2,mod-2); ll res=1;while(n>0){if(n&1)res=res*x%mod;n>>=1;x=x*x%mod;}return res;
}
int main()
{int n;scanf("%d",&n);rep(i,1,n+1)scanf("%I64d",&a[i]);ll cnt=0;for(int i=1;i<=n;++i){cnt=(cnt+(n+2-i)*mod_pow(2,n-1-i)%mod*a[i]%mod)%mod;}printf("%I64d",cnt);return 0;
}