写在前面: 这题我虽然把勉强能看的解释写出来了, 但是我自身感觉理解还是不够透彻, 解释也可能有疏漏和错误, 还麻烦发现的大佬提出一下QWQ
题目描述
小宇从历史书上了解到一个古老的文明。这个文明在各个方面高度发达，交通方面也不例外。考古学家已经知道，这个文明在全盛时期有 (n) 座城市，编号为 (1,2,cdots,n)。(m) 条道路连接在这些城市之间，每条道路将两个城市连接起来，使得两地的居民可以方便地来往。一对城市之间可能存在多条道路。
据史料记载，这个文明的交通网络满足两个奇怪的特征。
- 这个文明崇拜数字 (k)，对于任何一条道路，设它连接的两个城市分别为 (u) 和 (v)，则必定满足 (1 le leftvert {u-v} ightvert le k)。
- 任何一个城市都与恰好偶数条道路相连（ (0) 也被认为是偶数）。
不过，由于时间过于久远，具体的交通网络我们已经无法得知了。小宇很好奇这 (n) 个城市之间究竟有多少种可能的连接方法，于是她向你求助。
两种可能的连接方法不同当且仅当存在一对城市，它们间的道路数在两种方法中不同。
在交通网络中，有可能存在两个城市无法互相到达。
方法数可能很大，你只需要输出方法数模 (10^9 + 7) 后的结果。
输入格式
输入共一行，有三个整数 (n,m,k)。
输出格式
输出一个整数，表示方案数模 (10^9 + 7) 后的结果。
这是一个计数(DP)问题.
首先, 为了方便进行(DP), 我们设所有的边都是从下标较大的点指向下标较小的点的
设当前点的下标为 (i) , 然后因为 (k) 为下标之差, 我们建边时只能从 (i) 向 (left[i-k,i-1 ight]) 这个区间中建边
考虑到题中要求每个点必须连偶数条边, 那么, 对于该条件, 每个点只有连偶数条边和奇数条边两种状态, 且 (k) 范围较小, 我们可以采用状态压缩的思想, 将状态表示如下:
(eg.) (i-1) 连接了 (3) 条边, (S) 第 (1) 位 为 (1).
也就是我们每次考虑连边时, 只考虑 (left[i-k, i ight]) 中的点互相连边, 可以写出转移方程为:
在这个方程中有一个缺陷: 我们并不能确定这 j 条边加入的顺序, 所以我们最后求出来的并不是一个组合.
为了去重( 即保证连边顺序 ), 我们考虑添加一位状态 (t), 表示 (t) 状态下点 (i) 只能连接 (left[i-k, i-t-1 ight]) 的点.
也就是当前状态只能由第 (i-k) 个状态到第 (i-t-1) 个状态转移而来, 这样我们就可以固定边的连接顺序了.
现在, 我们再次考虑转移:
-
为了保证统计的正确, 我们需要倒序循环
-
若 (i) 和 (i-t-1) 不连边, 状态转移到考虑 (i-t-1) 的前一位, 即:
[fleft(i, j, S, t-1 ight) += fleft(i, j, S, t ight) ] -
若 (i) 和 (i-t-1) 连边, 则:
[fleft(i, j+1, S', t ight) += fleft(i, j, S, t ight), \ 其中 quad S' = S oplus 2^0 oplus 2^{t-1} ]- 其实 (S') 的式子就是把 (i) 和 (i-t-1) 两个位置的奇偶状态翻转.
-
循环边界: 若 (t=0) , 则:
[fleft(i+1, j, S'', min(i, k) ight) = fleft(i, j, S, t ight),\ 其中 quad S'' = Sll 1 ]- 注意: 在此种转移中, 我们要保证超出当前区间的那一位被连了偶数个边, 因为之后的状态都不会考虑这个点了, 也就是说, 我们要满足:[S & left(1ll k ight) = 0 ]
- 注意: 在此种转移中, 我们要保证超出当前区间的那一位被连了偶数个边, 因为之后的状态都不会考虑这个点了, 也就是说, 我们要满足:
这样我们就保证了刷表时更新答案的顺序, 从而达到了去重的效果.
时间复杂度: (Oleft(nmk cdot 2^k ight))
代码:
# include <iostream>
# include <cstdio>
# define MAXN 32
using namespace std;
int f[MAXN][MAXN][1<<9][MAXN];
const int MOD = 1e9+7;
int main(){
int n, m, k;
cin>>n>>m>>k;
f[1][0][0][0] = 1;
int tmp = 1<<k;
for(int i = 1; i <= n; i++){
for(int j = 0; j <= m; j++){
for(int S = 0; S < (1<<k+1); S++){
for(int t = min(i-1, k); t; t-- ){
(f[i][j][S][t-1] += f[i][j][S][t]) %= MOD;
if(i > t){
(f[i][j+1][S^1^(1<<t)][t] += f[i][j][S][t]) %= MOD;
}
}
if(!(S&tmp)){
(f[i+1][j][S<<1][min(i, k)] += f[i][j][S][0]) %= MOD;
}
}
}
}
cout<<f[n][m][0][0];
return 0;
}