首页 > 其他 > 详细

bzoj3195 [Jxoi2012]奇怪的道路

时间:2018-02-17 23:09:03      阅读:237      评论:0      收藏:0      [点我收藏+]

Description

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

据史料记载,这个文明的交通网络满足两个奇怪的特征。首先,这个文明崇拜数字 \(K\) ,所以对于任何一条道路,设它连接的两个城市分别为 \(u\)\(v\) ,则必定满足 \(1 \le |u - v| \le K\) 。此外,任何一个城市都与恰好偶数条道路相连( \(0\) 也被认为是偶数)。不过,由于时间过于久远,具体的交通网络我们已经无法得知了。小宇很好奇这 \(n\) 个城市之间究竟有多少种可能的连接方法,于是她向你求助。

方法数可能很大,你只需要输出方法数模 \(1000000007\) 后的结果。

Input

输入共一行,为 \(3\) 个整数 \(n,m,K\)

Output

输出 \(1\) 个整数,表示方案数模 \(1000000007\) 后的结果。

Sample Input

Case: 1

3 4 1

Case: 2

4 3 3

Sample Output

Case: 1

3

Case: 2

4

HINT

\(100\%\) 的数据满足 \(1 \le n \le 30, 0 \le m \le 30, 1 \le K \le 8\).

Solution

状压吼题。

发现 \(K\) 很小,于是考虑压一波 \(K\)

\(f[i][j][k][l]\) 表示正在考虑点 \(i\) ,已经连了 \(j\) 条边, 点 \(i - K\) 到 点 \(i\) 的度数状态为 \(k\) ,正在考虑点 \(i-K+l\) 与点 \(i\) 的连边。最终答案为 \(f[n+1][m][0][0]\)

考虑转移 \[f[i][j][k][l]\to \begin{Bmatrix}f[i][j][k][l+1] \\ f[i][j+1][k\oplus (1<<K) \oplus (1<<l)][l] \end{Bmatrix}\]

#include<bits/stdc++.h>
using namespace std;

#define mod 1000000007
#define rep(i, a, b) for (int i = a; i <= b; i++)

int f[40][40][1 << 9][9], n, m, K, bin[10] = { 1 };

int main() {
    rep(i, 1, 10) bin[i] = bin[i - 1] << 1;
    cin >> n >> m >> K;
    f[2][0][0][0] = 1;
    rep(i, 2, n) rep(j, 0, m) rep(k, 0, bin[K + 1] - 1) {
        rep(l, 0, K - 1) if (f[i][j][k][l]) {
            (f[i][j][k][l + 1] += f[i][j][k][l]) %= mod;
            if (i - K + l > 0 && j < m) (f[i][j + 1][k ^ bin[l] ^ bin[K]][l] += f[i][j][k][l]) %= mod;
        }
        if (!(k & 1) && f[i][j][k][K]) f[i + 1][j][k >> 1][0] = f[i][j][k][K];
    }
    cout << f[n + 1][m][0][0];
    return 0;
}

bzoj3195 [Jxoi2012]奇怪的道路

原文:https://www.cnblogs.com/aziint/p/8452296.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!