何人知的征程韦德娱乐1946手机版

3195: [Jxoi2012]不料的道路

Time Limit: 10 Sec  Memory
Limit: 128 MB

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

韦德娱乐1946手机版,【输入样例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.

【题目表明】三种可能的连年情势不同当且仅当存在一些城市,它们间的征程数在二种办法中不同。在交通网络中,有可能存在五个城市不可能相互到达。

 

题解:

测验的时候自己真的没有想到……看到了数量范围相比较小,但是我想的是深搜而不是状压……

咱俩发现k的多寡范围很小,所以大家考虑状压,首先考虑气象数组定义。

首先,f数组肯定有2维表示枚举到的罗列和边数。我们发现,题目中对各类点的奇偶性有限制,而奇偶是二种相反的定义,

故而我们品尝再用一位表示可以和这些点连边的点的出度奇偶性状态,1意味着奇;可是我们发现,假若那些装置为拥有它能更换来的点的奇偶性(一共16位),

不光时间复杂度变大,转移时候的议论也会很复杂,而我辈考虑一下,其实只弄一边的情景就可以了,从现在的点未来转移相当于从背后的点往前更换

所以大家只保留i点以及前边k个点的情状即可,我们再设置一维l,表示咱们已经考虑到了前方k+1个点中的第l个点(大家设高位离着i点近期,第0位是点i-k,第k位是i点,一共k+1位)

于是乎我们赢得了一个四维的情景数组,f[35][35][(1<<9)[10],接下去大家着想更换

设想对第i-k+l个点与第i个点,假诺我们不再加边,就径直转移到下一个f[i][j][state][l+1]

假设我们再还合法的事态下加边,会同时更改i点和i-k+l这三个的出度奇偶性,也就是更换来f[i][j+1][state^(1<<k)^(1<<l)][l]

接下来我们着想不同i之间的转换。假设当前意况要更换的话,大家现在第i-k个点永远不会再被考虑,因而转移的前提之一是第i-k位奇偶性是0,即state&1==0

再者,我们还可以够窥见一个很有用的属性:对于点i+1,它先河state就是第i个点的state>>1,这点很分明,从大家第3维的概念中就能来看这一操作可以实现

这样的话,就有跨第一维的转移,即向f[i+1][j][u>>1][0]转移

再最终的时候,输出f[n+1][m][0][0]即可,代码见下:

 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 typedef long long LL;
 5 const LL mod=1000000007;
 6 int n,m,k,bin[20],f[40][40][(1<<9)+10][10];
 7 int main()
 8 {
 9     scanf("%d%d%d",&n,&m,&k);
10     bin[0]=1;for(int i=1;i<=15;i++)bin[i]=bin[i-1]<<1;
11     f[2][0][0][0]=1;
12     for(int i=2;i<=n;i++)
13         for(int j=0;j<=m;j++)
14             for(int u=0;u<bin[k+1];u++)
15             {
16                 for(int l=0;l<k;l++)
17                     if(f[i][j][u][l])
18                     {
19                         (f[i][j][u][l+1]+=f[i][j][u][l])%=mod;
20                         if(j<m&&i-k+l>0)
21                             (f[i][j+1][u^bin[k]^bin[l]][l]+=f[i][j][u][l])%=mod;
22                     }
23                 if((u&1)==0&&f[i][j][u][k])
24                     f[i+1][j][u>>1][0]=f[i][j][u][k];
25             }
26     printf("%d",f[n+1][m][0][0]);
27 }

 

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图