A simple Blog for wyx I've been down the bottle hoping.
[Jxoi2012]奇怪的道路 状压$dp$
发表于: | 分类: Oi | 评论:0 | 阅读:41

小宇从历史书上了解到一个古老的文明。这个文明在各个方面高度发达,交通方面也不例外。考古学家已经知道,这个文明在全盛时期有$n$座城市,编号为$1..n$。$m$条道路连接在这些城市之间,每条道路将两个城市连接起来,使得两地的居民可以方便地来往。一对城市之间可能存在多条道路。
据史料记载,这个文明的交通网络满足两个奇怪的特征。首先,这个文明崇拜数字K,所以对于任何一条道路,设它连接的两个城市分别为$u$和$v$,则必定满足$1 \le |u - v| \le K$。此外,任何一个城市都与恰好偶数条道路相连($0$也被认为是偶数)。不过,由于时间过于久远,具体的交通网络我们已经无法得知了。小宇很好奇这n个城市之间究竟有多少种可能的连接方法,于是她向你求助。
方法数可能很大,你只需要输出方法数模$1000000007$后的结果。

显然影响一个点状态的点只有前面的$K$个
状压,$F(i,j,k)$表示到了第$i$个位置,前面$K$个的状态,当前处理的连边为 i 到 i - k + c 的方案数
然后随便转移就行了

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int mod = 1000000007;
int F[32][31][1<<11][10];
int main()
{
    int n,m,k;
    cin >> n >> m >> k;
    int Max = (1<<(k+1)) - 1;
    F[2][0][0][0] = 1;
    for(int i=2;i<=n;++i)
        for(int j=0;j<=m;++j)
            for(int sta=0;sta<=Max;++sta)
            {
                for(int l=0;l<k;++l)
                    if(F[i][j][sta][l])
                    {
                        (F[i][j][sta][l+1] += F[i][j][sta][l])%=mod;
                        if( i+l-k>0 && j+1 <= m)
                            (F[i][j+1][sta^(1<<l)^(1<<k)][l] += F[i][j][sta][l])%=mod;
                    }
                if(!(sta&1) && F[i][j][sta][k])
                    F[i+1][j][sta>>1][0] = F[i][j][sta][k];
            }
    cout << F[n+1][m][0][0] << endl;
}
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP