AGC045C Range Set
简单题。
显然初始全零和全一没有区别，可以全部进行一次覆盖，所以如果 $A>B$ 可以交换 $A,B$ 。
首先可以发现，如果打算在结尾放 $B$ 个 $1$ ，那么前面任意放的状态都可以被构造出来。因为总是可以用 $A$ 个 $0$ 去覆盖掉一部分的 $1$ 。
接着考虑，会发现如果在序列中任意存在一段连续 $B$ 个 $1$ ，那么它的左右的构造是互不影响的，都可以用一样的方法造出来。所以只要序列中存在一段连续 $B$ 个 $1$ 就一定可以构造出来。
如果序列中不存在连续 $B$ 个 $1$ ，有时也是可以被构造出来的。可以发现，如果有一段长度大于等于 $A$ 的 $0$ 序列，它其实可以是在最后把这段从 $1$ 变成 $0$ 的，因此可以把它看成一段 $1$ 。
如果顺着这个思路去想，可以发现对于一段连续的长度大于等于 $B$ 的 $1$ ，其实也可以看作是在最后通过将一段 $0$ 变成 $1$ 得到的。所以如果倒着思考这个问题，只要存在一段长度大于等于 $B$ 的 $1$ ，它总是可以交替进行变 $0$ 和变 $1$ 并且最终将整个序列回滚成 $0$ ，所以是一定可以被构造出来的。
所以倒着考虑，一个序列是否合法就变成了在开始时可以将长度大于等于 $A$ 的连续 $0$ 段变成 $1$ ，问是否可以造出一段长度大于等于 $B$ 的连续 $1$ 段。
显然，考虑反面更容易，考虑计数不可被构造出来的序列个数。也就是即使将所有大于等于 $A$ 的 $0$ 段反转成 $1$ ，也无法在序列中凑出一个长度大于等于 $B$ 的段。也就是说任何两个长度小于 $A$ 的 $0$ 段的间隔必须小于 $B$ 。这个问题可以简单地用 dp 解决。
设 $dp[i][0/1]$ 表示当前考虑到序列的第 $i$ 个位置，最后一段放的是长度小于 $A$ 的 $0$ 段还是长度小于 $B$ 的 $1+0$ 段，随便转移一下即可。
复杂度 $O(n^2)$ 。
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
| #include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "unordered_map"
#include "cassert"
#include "bitset"
#include "queue"
using namespace std;
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
const int MAXN = 5006;
const int P = 1e9 + 7;
int n , a , b;
int f[MAXN] , dp[MAXN][2];
void solve() {
cin >> n >> a >> b;
if( a > b ) swap( a , b );
f[0] = f[1] = 1;
rep( i , 2 , n ) {
f[i] = f[i - 1];
rep( j , 0 , i - a - 1 ) f[i] = ( f[i] + f[j] ) % P;
}
rep( i , 1 , a - 1 ) dp[i][0] = 1;
rep( i , 1 , b - 1 ) dp[i][1] = f[i];
rep( i , 1 , n ) {
rep( j , max( 1 , i - a + 1 ) , i - 1 ) dp[i][0] = ( dp[i][0] + dp[j][1] ) % P;
rep( j , max( 1 , i - b + 1 ) , i - 1 ) dp[i][1] = ( dp[i][1] + dp[j][0] * 1ll * f[i - j - 1] ) % P;
}
int ans = dp[n][0];
rep( i , n - b + 1 , n - 1 ) {
ans = ( ans + dp[i][0] * 1ll * f[n - i] ) % P;
}
int p2 = 1;
rep( i , 1 , n ) p2 = ( p2 + p2 ) % P;
cout << ( p2 + P - ans ) % P << endl;
}
signed main() {
solve();
}
|
