题面

现有 nn 位宾客围成一圈玩游戏。主办方准备了编号依次为 0,1,…,2k−10, 1, \dots, 2^k - 1 共 2k2^k 种面具（每种面具均有无数个），每位宾客都要穿上一个面具。游戏要求任意相邻的两位宾客，记他们面具上的编号分别为 ii 和 jj ，满足 i⊙j≠0i \odot j \neq 0 （注：⊙\odot 此处代表同或 XNOR，0⊙0=1⊙1=1,0⊙1=1⊙0=00 \odot 0 = 1 \odot 1 = 1, 0 \odot 1 = 1 \odot 0 = 0 ）。

试问有多少种方案？结果对 109+710^9 + 7 取模。

数据范围：

0<n,k≤1060 < n, k \le 10^6 。

题目链接

分析

根据同或性质不难发现，在本题条件下，i⊙j≠0i \odot j \neq 0 等价于 i+j≠2k−1i + j \neq 2^k - 1 。这也表明非法的两个编号奇偶性不同，故一定不相等。至于为什么随便举几个二进制下的例子就明白了……

考虑动态规划（有点类似于 HDUOJ - 1297 Children’s Queue）。

简单的方法

去网上搜了一篇题解才发现我是真的傻逼…… 呜呜呜。下面讲一讲较简单的方法。

分析

记 dp[i]dp[i] 代表有 ii 位宾客时的满足题意要求的方案数。

首先考虑第一位，显然有 2k2^k 种选择，然后剩余位数除了最后一位显然都有 2k−12^{k - 1} 种选择。

在考虑最后一位时，我们需要分情况讨论一下（记 aia_i 代表第 ii 位宾客面具种类）：

  • 如果 ai−1≠a1a_{i - 1} \neq a_1 ，那么 aia_i 不可以选 2k−1−ai−12^k - 1 - a_{i - 1} 或是 2k−1−a12^k - 1 - a_1 ，共有 2k−22^k - 2 种选择；
  • 如果 ai−1=a1a_{i - 1} = a_1 ，由于 2k−1−ai−1=2k−1−a12^k - 1 - a_{i - 1} = 2^k - 1 - a_1 ，所以有 2k−12^k - 1 种选择。

由于在考虑 ai−1≠a1a_{i - 1} \neq a_1 时已经计算过 2k−22^k - 2 种放法了，所以这里认为最后一个数字是一个定值（换句话说，再加一种就行了），所以我们还需要加上 dp[i−2]dp[i - 2] 。于是我们得到转移方程：

dp[i]=2k⋅(2k−1)i−2⋅(2k−2)+dp[i−2] dp[i] = 2^k \cdot (2^k - 1)^{i - 2} \cdot (2^k - 2) + dp[i - 2]

实现

完整参考代码 - 简单

麻烦的方法

不删是因为懒想纪念一下我有多蠢……嘤嘤嘤。

分析

我们记 ans[i]ans[i] 代表有 ii 位宾客时的满足题意要求的方案数，另外为了方便我们记 aia_i 为第 ii 位宾客面具上的编号。我们思考 ans[i]ans[i] 可被如何转化而来。

我们考虑已有 i−1i - 1 名宾客围成一圈的情况，并尝试在第 i−1i - 1 位宾客和第 11 位宾客间插入第 ii 名宾客。我们很快意识到 a1a_1 与 ai−1a_{i - 1} 是否相等影响着我们对 aia_i 选择的余地：

  • 若 a1≠ai−1a_1 \neq a_{i - 1} ，则我们不可以插入 2k−1−a12^k - 1 - a_1 或是 2k−1−ai−12^k - 1 - a_{i - 1} ，我们有 2k−22^k - 2 种选择；
  • 若 ai=ai−1a_i = a_{i - 1} ，则上面提到的两个数实际上是相等的，故我们有 2k−12^k - 1 种选择。

基于这一启发，我们不妨记 dp[i][0]dp[i][0] 代表 ii 位宾客玩游戏在满足题目要求前提下有 a1≠aia_1 \neq a_i 的情形数，而 dp[i][1]dp[i][1] 代表 ii 位宾客玩游戏在满足题目要求前提下有 a1=aia_1 = a_i 的情形数。不难得知：

ans[i]=dp[i][0]+dp[i][1] ans[i] = dp[i][0] + dp[i][1]

我们不妨先考虑 dp[i][1]dp[i][1] 如何推出：

  • 对于 dp[i−1][0]dp[i - 1][0] 描述的情况，由于 ai−1+a1≠2k−1a_{i - 1} + a_1 \neq 2^k - 1 ，所以可以直接在第 ii 位插入 a1a_1 使得首尾相等；
  • 对于 dp[i−1][1]dp[i - 1][1] 描述的情况，第 ii 位显然可以直接插入 a1a_1 ；

因此：

dp[i][1]=dp[i−1][0]+dp[i−1][1] dp[i][1] = dp[i - 1][0] + dp[i - 1][1]

接下来我们考虑 dp[i][0]dp[i][0] 如何推出：

先考虑 i−1i - 1 个宾客围成一圈可构成合法方案的情形：

  • 对于 dp[i−1][0]dp[i - 1][0] 描述的情况，第 ii 位我们不可以插入 a1a_1 、2k−1−a12^k - 1 - a_1 或是 2k−1−ai−12^k - 1 - a_{i - 1} ，因此我们有 2k−32^k - 3 种选择；
  • 对于 dp[i−1][1]dp[i - 1][1] 描述的情况，由于 2k−1−a1=2k−1−ai−12^k - 1 - a_1 = 2^k - 1 - a_{i - 1} ，因此我们有 2k−22^k - 2 种选择；

那么如果前 i−1i - 1 个宾客围成一圈不能构成合法方案呢？显然，问题只能出现在 ai−1+a1=2k−1a_{i - 1} + a_1 = 2^k - 1 （这便保证了 ai−1≠a1a_{i - 1} \neq a_1 ），而除此以外不能有其他位置出现非法情况。在这种情况下我们只需要在 ii 处插入除 2k−1−a12^k - 1 - a_1 和 2k−1−ai−12^k - 1 - a_{i - 1} 以外的值就可以得到合法情形了。我们有 2k−22^k - 2 种选择。

接下来我们需要解决的问题就是统计前 i−1i - 1 位宾客围成一圈满足上述情形的不合法方案有多少种。

显而易见的做法就是考虑不考虑首尾合法情况但考虑其余部分合法情况的总方案数（下文简称总方案数）减去合法方案数。显然，对于 ii 位宾客总方案数根据乘法原理有：

2k⋅(2k−1)i−1 2^k \cdot (2^k - 1)^{i - 1}

因此对于前 i−1i - 1 位宾客满足上述情形的不合法情况种数即：

2k⋅(2k−1)i−2−(dp[i−1][0]+dp[i−1][1]) 2^k \cdot (2^k - 1)^{i - 2} - (dp[i - 1][0] + dp[i - 1][1])

或者你也可以用分类讨论得到等效的一个结果：

  • 首先考虑前 i−2i - 2 位围成一圈合法：在此基础上 i−1i - 1 处插入 2k−1−a12^k - 1 - a_1 便是一类不合法方案，有 dp[i−2][0]dp[i - 2][0] 种；
  • 接着考虑前 i−2i - 2 位围成一圈不合法，但是前 i−3i - 3 位围成一圈合法：在此基础上 i−2i - 2 处和 i−1i - 1 处都插入 2k−1−a12^k - 1 - a_1 就又是一类不合法方案，有 dp[i−3][0]dp[i - 3][0] 种；
  • 接着考虑前 i−3i - 3 位围成一圈合法，但是前 i−4i - 4 位围成一圈合法：同理有 dp[i−4][0]dp[i - 4][0] 种；
  • …\dots

加在一起易知共有 ∑j=1i−2dp[j][0]\sum\limits_{j = 1}^{i - 2} dp[j][0] 种不合法情形。

上面两个式子是等价的。

实现

根据上面的分析，有：

{dp[i][0]=(2k−3)⋅dp[i−1][0]+(2k−2)⋅dp[i−1][1]+(2k−2)⋅[2k⋅(2k−1)i−2−(dp[i−1][0]+dp[i−1][1])]dp[i][1]=dp[i−1][0]+dp[i−1][1] \begin{cases} dp[i][0] & = (2^k - 3) \cdot dp[i - 1][0] + (2^k - 2) \cdot dp[i - 1][1] \\ & + (2^k - 2) \cdot \left[ 2^k \cdot (2^k - 1)^{i - 2} - (dp[i - 1][0] + dp[i - 1][1]) \right] \\ dp[i][1] & = dp[i - 1][0] + dp[i - 1][1] \end{cases}

至于初始化，显然：

{dp[0][0]=dp[0][1]=dp[1][1]=0dp[1][0]=2k \begin{cases} dp[0][0] = dp[0][1] = dp[1][1] = 0 \\ dp[1][0] = 2^k \\ \end{cases}

完整参考代码 - 麻烦

%%%