小宇从历史书上了解到一个古老的文明.这个文明在各个方面高度发达,交通方面也不例外.考古学家已经知道,这个文明在全盛时期有n座城市,编号为1..n.m条道路连接在这些城市之间,每条道路将两个城市连接起来,使得两地的居民可以方便地来往.一对城市之间可能存在多条道路. 据史料记载,这个文明的交通网络满足两个奇怪的特征.首先,这个文明崇拜数字K,所以对于任何一条道路,设它连接的两个城市分别为u和v,则必定满足1 <=|u - v| <= K.此外,任何一个城市都与恰好偶数条道路相连(0也被认为是偶数).不过,由于时间过于久远,具体的交通网络我们已经无法得知了.小宇很好奇这n个城市之间究竟有多少种可能的连接方法,于是她向你求助. 方法数可能很大,你只需要输出方法数模1000000007后的结果.
输出1个整数,表示方案数模1000000007后的结果.
两种可能的连接方法不同当且仅当存在一对城市,它们间的道路数在两种方法中不同.
在交通网络中,有可能存在两个城市无法互相到达.
这是一道我看不出来是状压的状压,而且连暴力然后打表都没搞出来(还是太弱啊),看WD的解题报告预测时间复杂度,然后确定他是个状压,水平不一样啊,不过实话来说,像这种不超过100的数据范围,最小的那个变量连10都没到,那状压其实也就八九不离十了,毕竟这么小的范围对别的算法来说都过于小了.
那状压的话就要有状态,它有一个奇偶的要求,就两种情况0和1两种状态,状压刚刚好,但是考试要想到啊!考试啊!考完想出来我都会,然后考试抱0蛋,没人搭理你啊!考试分高就是大哥,不然只能当弟弟,算了,连大哥解题报告都看不懂的人,大概只有当弟弟的分了,言归正传,0表示偶数,1表示奇数,为了保证无后效性这一要求,转移只转移第i个城市前面k个城市
左移$k$位则有$(k+1)$留$k$位则前一行的第$k+1$位直接被干掉了,不这么写的话,就需要判断前一行的第$k+1$位,如果为$1$直接舍去,奇数边且后面没有城市能跟他相连,与题意矛盾,左移$k$位就不需要特判.