很棒的计数DP题.

Description

若正整数集合$X \sub [1,n], Y \sub [1,M], X \cap Y = \empty$, 且有$\bigoplus_X < \bigoplus_Y$, 求方案数.

Solution

先考虑一个朴素的DP:

$f(i,j,k)$ 表示决策第$i$个数字, $\bigoplus_X = j, \bigoplus_Y = k$的方案数. 每次转移只要决策是把数字$i$给X, Y或者都不给即可.

最后取所有$j < k$的$f(\max(n,m), j, k)$即可. 这是$O(n^3)$的, 无法通过此题.

我们考虑枚举$X$和$Y$异或和的LCP, 那么对于枚举的长度$i$, 合法的状态一定是: $X \oplus Y$的高$i - 1$位均为0, 且$i$位为1, 且$X$第$i$位为0. 于是我们可以这样设计状态: $f(i,j,0/1)$表示决策第$i$个数, $X \oplus Y$为$j$, $X$的第$b$位为$0/1$, $b$是枚举的. 由于无论把$i$分给谁, 作用在$X \oplus Y$上的效果都是一样的, 所以我们可以削减状态量.

这样DP的复杂度就降到了$O(n^2\log{n})$.

题解还提出了更优的复杂度. 对于枚举到第$b$位的情况, 我们状态中只记录异或和的高$b$位, 这样总的复杂度就降到了$O(n^2)$.

WinterAndSnowmen.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>

using namespace std;

const int maxn = 2005;
const int maxs = (1 << 11);
const int mod = 1e+9 + 7;

int dp[maxn][maxs][2], n, m, cur;

class WinterAndSnowmen {
public:
  int f(int t, int x, int bt) {
    if (dp[t][x][bt] != -1) return dp[t][x][bt];
    int ret = 0;
    if (t == 0) {
      if (x == 1 && bt == 0)
        ret = 1;
      else ret = 0;
    } else {
      ret = f(t - 1, x, bt);
      if (t <= n) {
        ret = (ret + f(t - 1, x ^ (t >> cur), bt ^ ((t >> cur) & 1))) % mod;
      }
      if (t <= m) {
        ret = (ret + f(t - 1, x ^ (t >> cur), bt)) % mod;
      }
    }
    return dp[t][x][bt] = ret;
  }
  int getNumber(int N, int M) {
    n = N; m = M;
    int ans = 0;
    for (cur = 0; cur < 11; ++cur) {
      memset(dp, -1, sizeof dp);
      ans = (ans + f(max(n, m), 0, 0)) % mod;
    }
    return ans;
  }
};