CF1452D Radio Towers 题解

[可能更好的阅读体验](https://www.cnblogs.com/jiangtaizhe001/p/16920768.html) [题目传送门](http://codeforces.com/problemset/problem/1452/D) ### 题目大意 在数轴上有 $n+2$ 个小镇，位置为 $0,1,\dots,n,n+1$。 现在在 $1,2,\dots ,n$ 的小镇都有 $\dfrac{1}{2}$ 的概率建设一个信号发射器。 对于任意一个信号发射器，你都可以选择一个整数作为强度 $p$。如果一个信号发射器的位置是 $x$，那么位于 $[x-p,x+p]$ 的小镇都能收到一个信号。 现在求能够通过设置信号值，使 $1,2,\dots,n$ 恰好能接受到一个信号，$0,n+1$ 不能接受到信号的概率，对 $998244353$ 取模。 ### 题解 设 $f_i$ 为 $n=i$ 的时候的方案数。显然 $f_0=f_1=1$。 考虑如何转移 假设我们最后一个位置是 $i-j$。 那么显然这个位置的强度是 $j$，这样 $[i-j\times2,i]$ 这段区间就被覆盖了，此时的方案数就是 $f_{i-j\times 2}$。 枚举 $j$，我们可以知道 $$f_i=\sum_{j< i\ , i\not\equiv j\pmod 2}f_j$$ 所以只需要预处理 $i$ 模 $2$ 不同的前缀和就可以了。 ```cpp int n; ll f[maxn],s[2]; ll fastpow(ll x,ll y){ ll tmp=x,res=1; while(y){ if(y&1) res=res*tmp%MOD; tmp=tmp*tmp%MOD; y>>=1; } return res; } int main(){ int i; n=read(); f[0]=1; s[0]=1; f[1]=1; s[1]=1; for(i=2;i<=n;i++) f[i]=s[(i&1)^1],f[i]%=MOD,s[i&1]+=f[i],s[i&1]%=MOD; print(f[n]*fastpow(499122177,n)%MOD); return 0; } ```