题目传送门(BZOJ)

题意 :

英文题, 简述一下题意 :
给你一个数列, 让你从中选出两个集合 S, T
使得 S 的每个数都在 T 的前面, 并且 S 的异或和等于 T 的与和 (把所有数&起来)
求方案数, 取模 $10^9+7$

题解 :

对于与和异或, 分别做一遍DP, 一个从前往后, 一个从后往前, 然后枚举中间点合并求方案数即可
每个 DP 都是一个类似于 01 背包的东西, 用前缀和优化求一下即可
$f[i][j]$ 表示前面选到 $i$, 异或和为 $j$ 的方案数
$g[i][j]$ 方向相反,意义同理
f[i][j^a[i]] += s[j]
f[i][a[i]] ++
g[i][j&a[i]] += s[j]
g[i][a[i]] ++

然后前缀求 $f[x][j]$ 的和 $s[j]$

$ans += s[j]\times g[i+1][j]$
注意清空 $s$ 数组

代码 :

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define ll long longconst int N = 1100;const int p = 1e9+7;int f[N][N], g[N][N], s[N], a[N];inline void chplus(int &x, int y) { x = x+y; if(x>p) x -= p;}int main() { int T; scanf("%d", &T); while(T -- ) { memset(f, 0, sizeof f); memset(g, 0, sizeof g); memset(s, 0, sizeof s); int n; scanf("%d", &n); for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]); for(int i = 1; i < n; i ++ ) { for(int j = 0; j < 1024; j ++ ) chplus(f[i][j^a[i]], s[j]); chplus(f[i][a[i]], 1); for(int j = 0; j < 1024; j ++ ) chplus(s[j], f[i][j]); } memset(s, 0, sizeof s); for(int i = n; i > 1; i -- ) { for(int j = 0; j < 1024; j ++ ) chplus(g[i][j&a[i]], s[j]); chplus(g[i][a[i]], 1); for(int j = 0; j < 1024; j ++ ) chplus(s[j], g[i][j]); } memset(s, 0, sizeof s); ll ans = 0; for(int i = 1; i <= n; i ++ ) { for(int j = 0; j < 1024; j ++ ) chplus(s[j], f[i][j]); for(int j = 0; j < 1024; j ++ ) ans = (ans+(ll)s[j]*g[i+1][j])%p; } printf("%lld\n", ans); } return 0;}

本文为Yirannn原创, 转载必须以链接形式注明>原文链接<