BZOJ 3866: The Romantic Hero – [DP]


题目传送门(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 long
const 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原创, 转载必须以链接形式注明>原文链接<

发表评论

电子邮件地址不会被公开。 必填项已用*标注