题意简述

对于 $1$ 到 $n$ 的每个位置，都可以选择是否建造信号塔。

若在位置 $i$ 建造强度为 $p$ 的信号塔，则其覆盖区间为

$[i-p,\ i+p]$.

因此，一个合法方案可以看成若干个奇数长度区间的拼接。

tag:计数 动态规划

难度cf1350 洛谷普及

合法方案要求：

  1. 任意两个信号塔的覆盖区间不相交；
  2. 所有覆盖区间都不能超出 $[1,n]$；
  3. 每个位置以 $1/2$ 的概率建造信号塔。

求最终方案合法的概率。

思考

首先可以想到对于一个位置建不建造的选择有2种,所以所有情况就是 $2^n$,于是题目就转化为了计数问题,问有多少种情况合法最后乘上逆元就好了

于是题目就变成了求解找合法方案的个数,对于1到n的范围用长度只能是奇数的块覆盖,例如对于长的为5的块可以是长度为4的块加上一块或者长度为2的加上一个长度为3的块,和长度为0的块加长度为5的块就是

定义$f[i]$ 定义是长度为i的被完全覆盖的合法方案有多少种

考虑最后一个信号塔。假设它覆盖的区间长度为 $i-j$，
由于覆盖区间长度一定是奇数，所以 $i-j$ 必须为奇数。

前面的长度为 $j$ 的区间可以独立构成一个合法方案，
因此有：

$$f[i]=\sum_{\substack{0\le j<i\i-j\text{ 是奇数}}}f[j]$$

例如，当 $i=5$ 时，满足 $5-j$ 为奇数的 $j$ 有 $0,2,4$，
所以：

$$f[5]=f[0]+f[2]+f[4]$$

其中 $f[0]=1$ 表示空区间有一种方案，$f[1]=f[2]=1$ 是根据题目边界直接得到的初始情况.

当 $i$ 为奇数时，为了保证 $i-j$ 为奇数，$j$ 必须为偶数，因此 $f[i]$ 是所有偶数下标 $f[j]$ 的和。

当 $i$ 为偶数时，$j$ 必须为奇数，因此 $f[i]$ 是所有奇数下标 $f[j]$ 的和。

因此只需维护奇数下标和 sum_odd 以及偶数下标和 sum_even，即可在 $O(1)$ 时间内计算每个状态。

至于逆元的话直接用快速幂就好了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 998244353;

  

ll qpow(ll a, ll b, ll mod)

{

    ll res = 1;

    while (b > 0)

    {

        if (b & 1)

        {

            res = (res * a) % mod;

        }

        a = (a * a) % mod;

        b >>= 1;

    }

    return res;

}

  

void solve()

{

    ll n;

    cin >> n;

  

    vector<ll> f(n + 1, 0);

    f[0] = f[1] = f[2] = 1;

    ll sum_odd = 1, sum_even = 2;

    for (int i = 3; i <= n; i++)

    {

        if (i % 2 == 0)

        {

            f[i] = sum_odd % mod;

            sum_even = (sum_even + sum_odd) % mod;

        }

        else

        {

            f[i] = sum_even % mod;

            sum_odd = (sum_odd + sum_even) % mod;

        }

    }

  

    ll res = qpow(2, n, mod);

    res = qpow(res, mod - 2, mod);

  

    cout << (f[n] * res) % mod << endl;

}

int main()

{

    ll T = 1;

    // cin >> T;

  

    while (T--)

    {

        solve();

    }

}