hdu 4901 The Romantic Hero (dp)

2413 단어 dpHDU
제목은 하나의 서열을 두 개의 집합 A, B로 나누고 A의 모든 원소가 다르거나 다른 결과는 B의 모든 원소와 같은 결과로 나누어야 한다. 이런 구분 방안을 구한다. 주의해야 할 것은 제목이 요구하는 것이다. 이 두 집합의 원소는 임의의 i, jai에 대한 번호가 bj의 번호보다 작아야 한다.
사실은 배낭과 유사한 문제로 정추반추대의 방안수를 구하고 단점의 양쪽을 매거하여 곱하는 것이다.집합이 비어 있지 않도록 주의해라.
#include<iostream>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#define B(x) (1<<(x))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned ui;
const int oo = 0x3f3f3f3f;
//const ll OO = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define lson rt<<1
#define rson rt<<1|1
void cmax(int& a, int b){ if (b > a)a = b; }
void cmin(int& a, int b){ if (b < a)a = b; }
void cmax(ll& a, ll b){ if (b > a)a = b; }
void cmin(ll& a, ll b){ if (b < a)a = b; }
void cmax(double& a, double b){ if (a - b < eps) a = b; }
void cmin(double& a, double b){ if (b - a < eps) a = b; }
void add(int& a, int b, int mod){ a = (a + b) % mod; }
void add(ll& a, ll b, ll mod){ a = (a + b) % mod; }
const ll MOD = 1000000007;
const int maxn = 1100;
ll f[maxn][maxn][2], g[maxn][maxn][2];
int a[maxn];

int main(){
	int n, T;
	scanf("%d", &T);
	while (T--){
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)
			scanf("%d", &a[i]);
		memset(f, 0, sizeof f);
		memset(g, 0, sizeof g);
		for (int i = 1; i <= n; i++){
			f[i][a[i]][1] = 1;
			for (int j = 0; j < 1024; j++){
				f[i][j][0] += f[i - 1][j][0];
				f[i][j][0] += f[i - 1][j][1];
				f[i][j][0] %= MOD;
				f[i][j^a[i]][1] += f[i - 1][j][0];
				f[i][j^a[i]][1] += f[i - 1][j][1];
				f[i][j^a[i]][1] %= MOD;
			}
		}
		for (int i = n; i >= 1; i--){
			g[i][a[i]][1] = 1;
			for (int j = 0; j < 1024; j++){
				g[i][j][0] += g[i + 1][j][0];
				g[i][j][0] += g[i + 1][j][1];
				g[i][j][0] %= MOD;
				g[i][j&a[i]][1] += g[i + 1][j][0];
				g[i][j&a[i]][1] += g[i + 1][j][1];
				g[i][j&a[i]][1] %= MOD;
			}
		}
		ll ans = 0;
		for (int i = 1; i < n; i++){
			for (int j = 0; j < 1024; j++){
				ans += (f[i][j][1] * (g[i + 1][j][0] + g[i + 1][j][1]) % MOD) % MOD;
				ans %= MOD;
			}
		}
		cout << ans << endl;
	}
	return 0;
}

좋은 웹페이지 즐겨찾기