HihoCoder#1279 : Rikka with Sequence(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:\(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; }
上一篇: 网易薄荷移动直播平台宣布停运
下一篇: 你不做咨询太可惜了