hdu 4901 The Romantic Hero (dp)
사실은 배낭과 유사한 문제로 정추반추대의 방안수를 구하고 단점의 양쪽을 매거하여 곱하는 것이다.집합이 비어 있지 않도록 주의해라.
#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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.