CF1452D Radio Towers 题解

· · 题解

可能更好的阅读体验

题目传送门

题目大意

在数轴上有 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 不同的前缀和就可以了。

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