s2 NOIP模拟赛15-div2新太阳睡觉中心

新太阳睡觉中心

题面

原题链接

题解

简单计数题，但再给出一种与场上做法不一样的做法。

考虑总和转期望。将答案除以 \(2^k\)，则为将 \(-1\) 随机确定为 \(01\) 时答案的期望。

根据题目描述，我们对于每一段连续的 \(1\)，只统计其中第一个 \(1\) 的贡献，这样算出来的天数是最小天数。

显然 \(0\) 不可能带来贡献，\(1\) 则分以下几个情况。

1. 前面一个数是 \(0\) : 贡献为 \(1\) 。
2. 前面一个数是 \(1\) : 没有贡献。
3. 前面一个数是 \(-1\) : 有 \(\frac{1}{2}\) 的概率让前面这个 \(-1\) 为 \(0\)，则贡献为 \(\frac{1}{2}\)。

对于 \(-1\) 我们也分情况讨论。

1. 前面一个数是 \(0\) ：有 \(\frac{1}{2}\) 的概率成为合法 \(1\) ，贡献为 \(\frac{1}{2}\)
2. 前面一个数是 \(1\) : 不能成为合法 \(1\) ，贡献为 \(0\)。
3. 前面一个数是 \(-1\) : 有 \(\frac{1}{4}\) 的概率成为合法 \(1\) ，贡献为 \(\frac{1}{4}\) 。

统计完后将答案乘上 \(2^k\) ，就是原问题的答案。

总和转期望作为一种拆贡献的形式，在这题显然不是必要的，但我觉得它很好玩，同时这题也十分适合去理解总和转期望，遂记之awa。

const int mod=998244353;
const int N=5e5+5;
const int i2=499122177;
const int i4=748683265;
int n,a[N],T;
int qpow(int x,int b){int res=1;while(b){if(b&1) res=res*x%mod;x=x*x%mod;b>>=1;}return res;
}
void add(int &a,int b){a+=b;if(a>=mod) a-=mod;
}
void xpigeon(){cin>>n;int cnt=0;for(int i=1;i<=n;i++){cin>>a[i];if(a[i]==-1) cnt++;}int k=qpow(2,cnt);int ans=0;for(int i=1;i<=n;i++){if(a[i]==0) continue;if(a[i]==1){if(a[i-1]==0) add(ans,1);if(a[i-1]==-1) add(ans,i2);}if(a[i]==-1){if(a[i-1]==0) add(ans,i2);if(a[i-1]==-1) add(ans,i4);}}cout<<ans*k%mod<<'\n';
}