CF1452D Radio Towers（dp）

挺有意思的一道概率题

首先总方案数是已知的，因此就是求取合法方案

我们分析题目，发现1-n要被覆盖，且每个点只能被覆盖一次

这说明这题就是把整条线段分成奇数和的种类数

这种题一般都是dp题，要不就是组合数学大佬秒的

考虑一下暴力的dp，就是枚举前面合法状态去更新，并且要-1，-3这种因为我们要保证最后一段的分割是奇数

显然可以用前缀和优化，但是注意，这里需要分别维护奇偶前缀和

因为偶数点是从奇数点推过来的，而奇数点是由偶数点推过来的

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
typedef pair<int,int> plll;
const int N=2e5+10;
const int inf=0x3f3f3f3f;
const int mod=998244353;
ll s[N],f[N];
ll a[N];
ll qmi(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1){
            res=res*a%mod;
        }
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    int i;
    int n;
    cin>>n;
    a[0]=a[1]=1,a[2]=1;
    s[1]=1,f[2]=2;
    for(i=3;i<=n;i++){
        if(i&1){
            a[i]=(f[i-1])%mod;
            s[i]=(s[i-2]+a[i])%mod;
        }
        else{
            a[i]=s[i-1];
            f[i]=(f[i-2]+a[i])%mod;
        }
    }
    cout<<a[n]*qmi(qmi(2,n),mod-2)%mod<<endl;
}