BZOJ-3195: [Jxoi2012]奇怪的道路 (狀壓DP)

3195: [Jxoi2012]奇怪的道路

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 505  Solved: 327

[​​Submit​​​][​​Status​​​][​​Discuss​​]

Description

小宇從曆史書上了解到一個古老的文明。這個文明在各個方面高度發達，交通方面也不例外。考古學家已經知道，這個文明在全盛時期有n座城市，編号為1..n。m條道路連接配接在這些城市之間，每條道路将兩個城市連接配接起來，使得兩地的居民可以友善地來往。一對城市之間可能存在多條道路。

據史料記載，這個文明的交通網絡滿足兩個奇怪的特征。首先，這個文明崇拜數字K，是以對于任何一條道路，設它連接配接的兩個城市分别為u和v，則必定滿足1 <=|u - v| <= K。此外，任何一個城市都與恰好偶數條道路相連（0也被認為是偶數）。不過，由于時間過于久遠，具體的交通網絡我們已經無法得知了。小宇很好奇這n個城市之間究竟有多少種可能的連接配接方法，于是她向你求助。

方法數可能很大，你隻需要輸出方法數模1000000007後的結果。

Input

輸入共一行，為3個整數n，m，K。

Output

輸出1個整數，表示方案數模1000000007後的結果。

Sample Input

【輸入樣例1】

3 4 1

【輸入樣例2】

4 3 3

Sample Output

【輸出樣例1】

3

【輸出樣例2】

4

【資料規模】

HINT

100%的資料滿足1

<= n <= 30, 0 <= m <= 30, 1 <= K <= 8.

【題目說明】

兩種可能的連接配接方法不同當且僅當存在一對城市，它們間的道路數在兩種方法中不同。

在交通網絡中，有可能存在兩個城市無法互相到達。

Source

1 #include "bits/stdc++.h"
 2 using namespace std;
 3 typedef long long LL;
 4 const int mod=1000000007;
 5 int n,m,K,f[35][35][1<<9][10];//f[i][j][k][l]表示考慮到點i,用了j條邊,i-K到i的奇偶性為k,目前處理i-K+l和i之間的連邊。
 6 int main(){
 7     freopen ("road.in","r",stdin);freopen ("road.out","w",stdout);
 8     int i,j,k,l;
 9     scanf("%d%d%d",&n,&m,&K);
10     f[2][0][0][0]=1;
11     for (i=2;i<=n;i++)
12         for (j=0;j<=m;j++)
13             for (k=0;k<(1<<(K+1));k++){
14                 for (l=0;l<K;l++)
15                     if (f[i][j][k][l]){
16                         (f[i][j][k][l+1]+=f[i][j][k][l])%=mod;
17                         if (j<m && i-K+l>0)
18                             (f[i][j+1][k^(1<<K)^(1<<l)][l]+=f[i][j][k][l])%=mod;
19                     }
20                 if ((k&1)==0 && (f[i][j][k][l])) f[i+1][j][k>>1][0]=f[i][j][k][l];
21             }
22     printf("%d",f[n+1][m][0][0]);
23     return 0;
24