SPOJ16636 Journey IE2

更好的阅读体验

在Byteland有n个城市，编号从1到n。这些城市由m条双向道路网络连接。众所周知，每一对城市最多只能由一条道路连接。
Byteman最近承认，他喜欢某些城市多于其他城市。更确切地说，他在数字为1到k的城市中花费的时间特别多，所以在每次旅行中，他至少要访问其中的每个城市一次。
Byteman的旅程是一个由d个城市组成的序列，使得每一对连续的城市都由一条道路连接。旅程可以在任何城市开始和结束。你的任务是计算Byteman可以围绕Byteland进行的不同旅程的数量。因为这个数字可能相当大，所以只需找到1e9+9的模数即可。

• 题目来源：SPOJ16636 Journey IE2
• 算法一：
  • 我会暴力！
  • 复杂度 \(O(nd)\) 期望得分20
• 算法二：
  • 在之前基础上特判k=0 DP+矩阵优化
  • 设 \(f(i,j)\) 为 \(i\) 时刻在城市 \(j\) 的方案数，然后矩阵乘法优化
  • 复杂度 \(O(n^3\log_2d)\) 期望得分30
• 算法三：
  • 对于测试点3、4 状压DP
  • DP 时除了记录当前点，再记录关键城市是否到过
  • 我故意把这几个点的数据做得较水，应该能过
  • 复杂度 \(O(dnm \times 2^k)\) 期望得分50
• 算法四：
  • DP+矩阵优化+容斥
  • 同算法2 的DP，先暂且不理k 个重要城市，构建矩阵
  • 用容斥解决重要城市的问题，由于 \(k\) 最多只有 \(7\)，所以 \(2k\) 枚举重要城市｛可以经过/强制不能经过｝，强制不能经过只需在构建矩阵时无视与这个城市相连的边就行了
  • 最后 ans=f 强制关闭0 个重要城市-f 强制关闭1 个重要城市+f 强制关闭2 个重要城市-f 强制关闭3 个重要城市 +... ...
  • 复杂度 \(O(n^3\log_2d \times 2k)\) 期望得分100
• 算法五：
  • 这个位置留给大家了
  • 我的算法在SPOJ 上总运行时间17.24s 垫底，rank1 的运行时间1.75s
  • 所以我的做法显然不是标准算法