题意 ： 初始时，在黑板上写有 到 中的所有整数。
每次你可以选中一个
中还在黑板上的整数
，把它擦去并补写上 与 （如果原来不存在的话）。
你可以进行这个操作任意次（可以不进行），求最终黑板上数字的可能状态有多少种，答案对给定整数
取模。
，时限 。
为了方便考虑，将擦去改成写上。
初始时，黑板上没有数。每次可以选中 中一个不存在的数 ，将其写到黑板上，再擦去 （若存在）
考虑如何判定一种状态能否达到。
若最终 在黑板上，则 一定要后于 与 被写上，因为两者被写上时会擦去 。
于是，连边 和
，这个有向图的每一个拓扑序都是一种合法的书写方案，若有向图中有环，则无解。
现在问题能转化为：问
的多少个子集形成的有向图是无环的。
先把
的完整图画出来，观察会产生怎样的环：
（from @关怀他人）（这张图是 为奇数的情况）
将奇数和偶数分别画成两排。（记偶数集合为 ，奇数集合为 ）
若
为偶数，则在一排中选择达到
个连续的数，就会形成环。
两条链互不干涉，方案数是乘起来的。对于每条链分别简单 即可。
若 为奇数，则如上图。将
的边画在两条链中间。
不难发现，只需要考虑那些含有两条横边的环。
所有的环都形如 ：
从左侧某个点开始，向上走一段，向右走一次，向上走一段，回到原点。
如图中 。
考虑 。设 表示考虑了前
层（如图中横着的边），最长上右上路径长度达到 ，右侧偶数链连续选数 个的方案数。
若 达到 ，则会产生一个环。
选中左侧奇数，可以延续右上右路径（前提是得有）
当左侧奇数不选时，会切断上右上路径。
当左侧奇数和右侧偶数同时选中时，会产生新的右上右路径，长度为 。
具体转移见代码。
复杂度 。
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
| #include <algorithm>
#include <cstdio>
const int MaxN = 155;
int f[MaxN/2][MaxN][MaxN/2], g[MaxN/2][MaxN/2], pw2[MaxN/2];
int solve0(int N, int K, int mod) {
g[0][0] = 1;
K /= 2;
for (int i=0; i<(N+1)/2; i++)
for (int j=0; j<=std::min(i,K); j++) {
if (j+1<=K)
g[i+1][j+1] = (g[i+1][j+1]+g[i][j]) %mod;
g[i+1][0] = (g[i+1][0]+g[i][j]) %mod;
}
int ans1 = 0, ans2 = 0;
for (int i=0; i<=K; i++) {
ans1 = (ans1+g[N/2][i]) %mod;
ans2 = (ans2+g[(N+1)/2][i]) %mod;
}
return 1ll*ans1*ans2 %mod;
}
int solve1(int N, int K, int mod) {
pw2[0]=1;
for (int i=1; i<(K/2); i++)
pw2[i] = (pw2[i-1]*2) %mod;
for (int i=0; i<=(K/2); i++)
f[0][0][i] = pw2[std::max((K/2)-i-1,0)];
for (int i=1; 2*i-1<=N; i++)
if (2*i-1+K<=N) {
for (int j=0;j<=K+1;j++)
for (int k=0;k<=N/2;k++)
if (f[i-1][j][k]) {
int sav = f[i-1][j][k];
if (j>0) {
f[i][0][0] = (f[i][0][0]+sav) %mod;
f[i][0][k+1] = (f[i][0][k+1]+sav) %mod;
f[i][j+1][0] = (f[i][j+1][0]+sav) %mod;
f[i][j+1][k+1] = (f[i][j+1][k+1]+sav) %mod;
} else {
f[i][0][0] = (f[i][0][0]+2ll*sav) %mod;
f[i][0][k+1] = (f[i][0][k+1]+sav) %mod;
f[i][k+2][k+1] = (f[i][k+2][k+1]+sav) %mod;
}
}
} else {
for (int j=0; j<=K+1; j++)
for (int k=0; k<=N/2; k++)
if (f[i-1][j][k]) {
int sav = f[i-1][j][k];
if (j>0) {
f[i][0][0] = (f[i][0][0]+sav) %mod;
f[i][j+1][0] = (f[i][j+1][0]+sav) %mod;
} else
f[i][0][0] = (f[i][0][0]+2ll*sav) %mod;
}
}
int ans = 0;
for (int j=0; j<=K+1; j++)
for (int k=0; k<=N/2; k++)
ans = (ans+f[(N+1)/2][j][k]) %mod;
return ans;
}
int main() {
int N, K, mod;
scanf("%d%d%d", &N, &K, &mod);
printf("%d", K&1 ? solve1(N, K, mod) : solve0(N, K, mod));
return 0;
}
|