CF1452D Radio Towers

作者: MayFlyyh 分类: DP 发布时间: 2020-11-21 11:17 ė 6 没有评论

CF1452D Radio Towers

n +2 个点,编号从 0 开始,线性排列,从点 1n 每个点被取到的概率为 \large \frac{1}{2} ,求能产生合法覆盖的概率对 998244353 取模。

每个点若向左覆盖了 x个点,则他必须同时向右覆盖 x 个点,即覆盖范围 [i – x,i + x] ( x 由自己决定)

当每个点仅被覆盖一次,且点 0 和点 n-1 不被覆盖时,覆盖合法。

由于每个点选和不选的概率都是 \large \frac{1}{2} ,所以只需要用最后总方案数除以 2^{n} 即可

只考虑计算方案数

一个点能覆盖的距离为:1,3,5,7,9,11……

相当于每个点都能覆盖长度为奇数的一段

考虑 dp

i 为奇数,dp(i)=dp(i-1)+dp(i-3)+….+dp(0)

i 为偶数,dp(i)=dp(i-1)+dp(i-3)+….+dp(1)

为什么呢,因为可以考虑长度为 i 的方案可以通过 i-1 的方案后补一个覆盖长度为 1 的 灯,也可以通过 i-3 的方案后补一个覆盖长度为 3 的 灯,以此类推。

然后通过观察就可以发现

dp(i)=dp(i-1)+dp(i-2)

于是就是斐波那契数列

然后乘个逆元就好,复习一下

因为当 ap互质,有 a^{p-1}\equiv 1(mod p)

所以 a*a^{p-2} \equiv1(modp)

所以 a 关于 p 的逆元是 a^{p-2}

#include<bits/stdc++.h>
#define ll long long
const int mod = 998244353;
const int N = 2e5+10;
int a[N],n;
ll qpow(ll a,ll b,ll c){
    if(b==0)
        return 1ll;
    ll t=qpow(a,b/2,c);
    t=t*t%mod;
    if(b&1) t=t*a%mod;
    return t;   
}
int main(){
    scanf("%d",&n);
    a[1]=a[2]=1;
    for(int i=3;i<=n;++i)
        a[i]=(a[i-1]+a[i-2])%mod;
    ll b=qpow(2,n,mod);
    ll c=qpow(b,mod-2,mod);
    ll ans=a[n]*c%mod;
    printf("%lld",ans);
    return 0;
} 

本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。

本文永久链接: http://www.mayflyyh.com/archives/699

0

发表评论

电子邮件地址不会被公开。

Captcha Code

Ɣ回顶部