写在前面: 这题我虽然把勉强能看的解释写出来了, 但是我自身感觉理解还是不够透彻, 解释也可能有疏漏和错误, 还麻烦发现的大佬提出一下QWQ

题目描述

小宇从历史书上了解到一个古老的文明。这个文明在各个方面高度发达，交通方面也不例外。考古学家已经知道，这个文明在全盛时期有 \(n\) 座城市，编号为 \(1,2,\cdots,n\)。\(m\) 条道路连接在这些城市之间，每条道路将两个城市连接起来，使得两地的居民可以方便地来往。一对城市之间可能存在多条道路。

据史料记载，这个文明的交通网络满足两个奇怪的特征。

1. 这个文明崇拜数字 \(k\)，对于任何一条道路，设它连接的两个城市分别为 \(u\) 和 \(v\)，则必定满足 \(1 \le \left\vert {u-v}\right\vert \le k\)。
2. 任何一个城市都与恰好偶数条道路相连（ \(0\) 也被认为是偶数）。

不过，由于时间过于久远，具体的交通网络我们已经无法得知了。小宇很好奇这 \(n\) 个城市之间究竟有多少种可能的连接方法，于是她向你求助。

两种可能的连接方法不同当且仅当存在一对城市，它们间的道路数在两种方法中不同。

在交通网络中，有可能存在两个城市无法互相到达。

方法数可能很大，你只需要输出方法数模 \(10^9 + 7\) 后的结果。

输入格式

输入共一行，有三个整数 \(n,m,k\)。

输出格式

输出一个整数，表示方案数模 \(10^9 + 7\) 后的结果。

这是一个计数\(DP\)问题.

首先, 为了方便进行\(DP\), 我们设所有的边都是从下标较大的点指向下标较小的点的

设当前点的下标为 \(i\) , 然后因为 \(k\) 为下标之差, 我们建边时只能从 \(i\) 向 \(\left[i-k,i-1\right]\) 这个区间中建边

考虑到题中要求每个点必须连偶数条边, 那么, 对于该条件, 每个点只有连偶数条边和奇数条边两种状态, 且 \(k\) 范围较小, 我们可以采用状态压缩的思想, 将状态表示如下:

\(eg.\) \(i-1\) 连接了 \(3\) 条边, \(S\) 第 \(1\) 位 为 \(1\).

也就是我们每次考虑连边时, 只考虑 \(\left[i-k, i\right]\) 中的点互相连边, 可以写出转移方程为:

在这个方程中有一个缺陷: 我们并不能确定这 j 条边加入的顺序, 所以我们最后求出来的并不是一个组合.

为了去重( 即保证连边顺序 ), 我们考虑添加一位状态 \(t\), 表示 \(t\) 状态下点 \(i\) 只能连接 \(\left[i-k, i-t-1\right]\) 的点.

也就是当前状态只能由第 \(i-k\) 个状态到第 \(i-t-1\) 个状态转移而来, 这样我们就可以固定边的连接顺序了.

现在, 我们再次考虑转移:

• 为了保证统计的正确, 我们需要倒序循环

• 若 \(i\) 和 \(i-t-1\) 不连边, 状态转移到考虑 \(i-t-1\) 的前一位, 即:

  \[f\left(i, j, S, t-1\right) += f\left(i, j, S, t\right)
  \]

• 若 \(i\) 和 \(i-t-1\) 连边, 则:

  \[f\left(i, j+1, S', t\right) += f\left(i, j, S, t\right), \\
  其中 \quad S' = S \oplus 2^0 \oplus 2^{t-1}
  \]
  • 其实 \(S'\) 的式子就是把 \(i\) 和 \(i-t-1\) 两个位置的奇偶状态翻转.

• 循环边界: 若 \(t=0\) , 则:

  \[f\left(i+1, j, S'', min(i, k)\right) = f\left(i, j, S, t\right),\\
  其中 \quad S'' = S\ll 1
  \]
  • 注意: 在此种转移中, 我们要保证超出当前区间的那一位被连了偶数个边, 因为之后的状态都不会考虑这个点了, 也就是说, 我们要满足:
    \[S \& \left(1\ll k\right) = 0
    \]

这样我们就保证了刷表时更新答案的顺序, 从而达到了去重的效果.

时间复杂度: \(O\left(nmk \cdot 2^k\right)\)

代码:

# 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;
}