HDU 4901 The Romantic Hero(DP)

HDU 4901 The Romantic Hero

題目鏈接

題意：給定一個序列，要求找一個分界點，然後左邊選一些數異或和，和右邊選一些數且和相等，問有幾種方法

思路：dp，從左往右和從右往左dp，求出異或和且的個數，然後找一個分界點，使得一邊必須在分界點上，一邊隨意，然後根據乘法原理和加法原理計算

代碼：

#include 
#include 

typedef __int64 ll;
const int N = 1024;
const int M = 2048;

const int MOD = 1000000007;

int t, n, a[N], l[N][M], r[N][N], ls[N][M], rs[N][N];

int main() {
    scanf("%d", &t);
    while (t--) {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	    scanf("%d", &a[i]);
	memset(l, 0, sizeof(l));
	memset(ls, 0, sizeof(ls));
	l[1][a[1]] = ls[1][a[1]] = 1;
	for (int i = 2; i <= n; i++) {
	    for (int j = 0; j < M; j++)
		l[i][a[i]^j] = (l[i][a[i]^j] + ls[i - 1][j]) % MOD;
	    l[i][a[i]] = (l[i][a[i]] + 1) % MOD;
	    for (int j = 0; j < M; j++)
		ls[i][j] = (ls[i - 1][j] + l[i][j]) % MOD;
	}
	memset(r, 0, sizeof(r));
	memset(rs, 0, sizeof(rs));
	r[n][a[n]] = rs[n][a[n]] = 1;
	for (int i = n - 1; i >= 1; i--) {
	    for (int j = 0; j < N; j++)
		r[i][a[i]&j] = (r[i][a[i]&j] + rs[i + 1][j]) % MOD;
	    r[i][a[i]] = (r[i][a[i]] + 1) % MOD;
	    for (int j = 0; j < N; j++)
		rs[i][j] = (rs[i + 1][j] + r[i][j]) % MOD;
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++)
	    for (int j = 0; j < N; j++) {
		ans += ((ll)ls[i][j] * r[i + 1][j] % MOD);
		ans %= MOD;
	    }
	printf("%I64d\n", ans);
    }
    return 0;
}