HihoCoder#1279:RikkawithSequence(dp枚举子集二进制神仙题)

题意

题目链接

Sol

不愧是dls出的比赛啊，265个交了题的人只有8个有分Orz

做完这题，，感觉自己的位运算dp姿势升华了。。。

首先最裸的dp应该比较好想，设(f[i][j][k])表示前(i)个数选出来的数异或和为(j)，按位与和为(k)的方案数

转移的时候讨论一下该位置选不选，最后只要统计(f[N][i][i])的答案

比较坑的是这题在写的时候不能用一般的pull写法，也就是说不能从前面的状态转移而来，因为我们不知道应该从哪儿转移而来。

仔细想想也比较显然，就拿与运算来说，它在运算过程中会丢失掉一部分信息

比如(k = 1001, a[i] = 1011)，我们不清楚他是从(1101)转移而来还是(1001)转移而来。

时间复杂度：(O(n * 8192 * 8192) = GG)

int N, a[MAXN], Lim = 128, f[2][1235][1235];main() {    N = read();    for(int i = 1; i <= N; i++) a[i] = read();    f[0][0][Lim - 1] = 1;    int o = 0;    for(int i = 1; i <= N; i++, o ^= 1) {        for(int j = 0; j < Lim; j++)             for(int k = 0; k < Lim; k++)                 f[o ^ 1][j][k] = f[o][j][k];                    for(int j = 0; j < Lim; j++)             for(int k = 0; k < Lim; k++)                 f[o ^ 1][j ^ a[i]][k & a[i]] += f[o][j][k];    }    int ans = 0;    for(int i = 0; i <= Lim; i++) ans += f[o][i][i];    cout << ans;    return 0;}

接下来是神仙优化部分：

先考虑简单一点的。

显然，如果选出来的数与起来的第(i)位为(1)，那么显然所有数的这一位都为(1)。

如果我们再知道数的个数奇偶性，那么就可以知道这种情况是否合法。同理，若这一位是0，也可以按照奇偶性判断

复杂度：(O(2 * N * 13 * 8192))

事实上，转移是可以优化到O(1)的。

设(x)为选出来的数的异或和，(y)为选出来的数的按位与

若选出来的数为偶数个，那么(x & y = 0)

若选出来的数为奇数个，那么(x & y = y)

那么每个位上的状态都可以由一个三元组((xx, y, k))表示

1. 都为1：(xx = 0, y = 0)

2. 有奇数个1：(xx = 1, y = 0)

3. 有偶数个1：(xx = 0, y = 0)

再加上奇偶性(这个不需要压在状态里面)，总的状态数为(2 times 3^{13})

我们可以预处理出所有的(S(xx, y))的状态，转移的时候直接加上就行了。

最终的答案 = (f[N][S(0, 0)][0]) + (sum f[N][i][1] (xor[i] = 0))

做题的时候我对(y)和(xx)之间的关系纠结了好久

很显然，(xx)的二进制表示是(y)的补码的子集

因为(xx)是不考虑所有位都为1的情况的，而其余的位置又没有限定

另外就是(x)与(xx)的相互转化

• (x) to (xx)

如果(k)是奇数，那么(x = xx | y)，否则(x = xx)

可以直接由最开始的结论得到

• (xx) to (x)

xx = x & (-y)

可以直接由定义得到

比着一份极其风骚的代码抄了一遍。。。

可能还有一些神奇的逻辑关系没有注意到。。有空再看看。

#include#define file(x) freopen(x, "r", stdin);#define LL long longconst int MAXN = 2e6 + 10, Lim = 8192, INF = 1e9 + 7;using namespace std;inline int read() {    int x = 0, f = 1; char c = getchar();    while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();    return x * f;}int N, tot, a[51], And[MAXN], Xor[MAXN], S[Lim + 1][Lim + 1];LL f[2][MAXN][2];void Pre() {    for(int i = 0; i < 8192; i++) {        int x = (~i) & (Lim - 1);        for(int j = x; ; j = (j - 1) & x) {            And[tot] = i; Xor[tot] = j; S[j][i] = tot++;            if(j == 0) break;        }    }}main() {//  file("a.in")    N = read();    for(int i = 1; i <= N; i++) a[i] = read();    Pre();    int o = 0; f[0][S[0][Lim - 1]][0] = 1;    for(int i = 1; i <= N; i++, o ^= 1) {        int nxt = o ^ 1;        for(int j = 0; j < tot; j++)             f[nxt][j][0] = f[o][j][0],            f[nxt][j][1] = f[o][j][1];        for(int j = 0; j < tot; j++) {            for(int k = 0; k < 2; k++) {                if(!f[o][j][k]) continue;                int x = Xor[j], y = And[j];                if(k) x = x | y;                x ^= a[i]; y &= a[i]; x &= (~y);            //  printf("%d %d %dn", x, y, S[x][y]);                f[nxt][S[x][y]][!k] += f[o][j][k];            }        }    }    LL ans = f[o][S[0][0]][0];    for(int i = 1; i < tot; i++) if(Xor[i] == 0) ans += f[o][i][1];    cout << ans;    return 0;}