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

程序员文章站 2023-12-23 23:33:27

题意 "题目链接" Sol 不愧是dls出的比赛啊，265个交了题的人只有8个有分Orz 做完这题，，感觉自己的位运算dp姿势升华了。。。首先最裸的dp应该比较好想，设$f[i][j][k]$表示前$i$个数选出来的数异或和为$j$，按位与和为$k$的方案数转移的时候讨论一下该位置选不选，最后只 ......

题意

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：$xx = 0, y = 0$
有奇数个1：$xx = 1, y = 0$
有偶数个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<bits/stdc++.h>
#define file(x) freopen(x, "r", stdin);
#define ll long long
const 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 %d\n", 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;
}

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

题意

sol