HDU5909 FWT 가속 이질적 또는 볼륨
먼저 간단한 트리 DP D P는 dp[u][i][i]dp[u][i]로 u를 뿌리로 하는 하위 트리를 나타내고 모든 노드의 값이 다르거나 ii로 시작하는 방안 트리를 고려합니다.그러면 이동 dp[u][i]=∑v∈son(u)dp[v][j][u][i xor j]dp[u][i][i]=∑v∈son(u)dp[v][j]\dp[u][i][ixorj]가 존재한다.그렇다면 폭력의 복잡도는 O(n ∗ m ∗m) O(n ∗ m ∗m)다.그 다음에 그 이상 또는 볼륨은 FWT로 가속할 수 있다. 복잡도 O(n ∗ m ∗ logm) O(n ∗ m ∗ l o g m).
#define others
#ifdef poj
#include
#include
#include
#include
#include
#include
#include
#include
#include
#endif // poj
#ifdef others
#include
#endif // others
//#define file
#define all(x) x.begin(), x.end()
using namespace std;
#define eps 1e-8
const double pi = acos(-1.0);
typedef long long LL;
typedef unsigned long long ULL;
void umax(int &a, int b) {
a = max(a, b);
}
void umin(int &a, int b) {
a = min(a, b);
}
int dcmp(double x) {
return fabs(x) <= eps?0:(x > 0?1:-1);
}
void file() {
freopen("data_in.txt", "r", stdin);
freopen("data_out.txt", "w", stdout);
}
namespace solver {
const LL mod = 1e9+7;
const LL maxn = 1025;
const LL rev = 500000004;
LL t;
LL n, m;
LL val[maxn];
vector G[maxn];
LL dp[maxn][maxn];
LL ans[maxn];
LL Pow(LL a, LL b) {
LL res = 1;
while(b) {
if(b & 1) res *= a, res%= mod;
b >>= 1;
a *= a;
a %= mod;
}
return res;
}
void FWT(LL a[],LL n) {
for(LL d=1;d1)
for(LL m=d<<1,i=0;ifor(LL j=0;j//xor:a[i+j]=x+y,a[i+j+d]=(x-y+mod)%mod;
//and:a[i+j]=x+y;
//or:a[i+j+d]=x+y;
}
}
void UFWT(LL a[],LL n) {
for(LL d=1;d1)
for(LL m=d<<1,i=0;ifor(LL j=0;j1LL*(x+y)*rev%mod,a[i+j+d]=(1LL*(x-y)*rev%mod+mod)%mod;
//xor:a[i+j]=(x+y)/2,a[i+j+d]=(x-y)/2;
//and:a[i+j]=x-y;
//or:a[i+j+d]=y-x;
}
}
void solve(LL a[],LL b[],LL n) {
FWT(a,n);
FWT(b,n);
for(LL i=0;i1LL*a[i]*b[i]%mod;
UFWT(a,n);
}
void dfs(LL u, LL fa = -1) {
dp[u][val[u]] = 1;
for(auto v:G[u]) {
if(v == fa) continue;
dfs(v, u);
LL tmp[1025] = {0};
for(LL j = 0; j < m; j++) tmp[j] = dp[u][j];
// for(LL j = 0; j < m; j++)
// for(LL k = 0; k < m; k++)
// dp[u][j] += dp[v][k] * tmp[j^k];
solve(tmp, dp[v], m);
for(LL i = 0; i < m; i++) dp[u][i] += tmp[i];
}
for(LL i = 0; i < m; i++) ans[i] += dp[u][i], ans[i] %= mod;
}
void solve() {
// cout<
scanf("%lld", &t);
while(t--) {
for(LL i = 0; i < maxn; i++) G[i].clear();
memset(dp, 0, sizeof dp);
memset(ans, 0, sizeof ans);
scanf("%lld%lld", &n, &m);
for(LL i = 1; i <= n; i++) scanf("%lld", &val[i]);
for(LL i = 1; i <= n - 1; i++) {
LL x, y;
scanf("%lld%lld", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1);
for(LL i = 0; i < m; i++)
printf("%lld%c", ans[i], i == m - 1?'
':' ');
}
}
}
int main() {
// file();
solver::solve();
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
백준 10844번 쉬운 계단 수 - node.js문제 설명 계단수: 인접한 모든 자리의 차이가 1인 수 (EX. 로직 설명 N = 2일 때 가능한 계단수를 생각해보자. 해당 숫자들을 보면 십의자리 숫자들은 일의자리 숫자가 무엇이 오는지에 따라 올 수 있는 단어들이...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.