0%

数据结构模板系列——子集前缀后缀和与差分

  • 枚举子集,子集前缀、后缀和以及子集前缀、后缀差分模板。
  • 枚举子集模板,假设 i 为集合的二进制表示
1
for (j = i; j > 0; j = (j - 1) & i) {}
  • 子集前缀和主要是解决形如 c(S)=QSc(Q)c'(S)=\sum_{Q\subset S}c(Q) 问题的方法。
1
2
3
4
5
for (int i = 0; i < n; ++i>) {
for (int j = 0; j < (1 << n); ++j) {
if (j&(1 << i)) { c[j] += c[j ^ (1 << i)]; }
}
}
  • 子集前缀差分主要是已知上述 c’, 求出 c 的方法。
1
2
3
4
5
for (int i = 0; i < n; ++i>) {
for (int j = 0; j < (1 << n); ++j) {
if (j&(1 << i)) { c[j] -= c[j ^ (1 << i)]; }
}
}
  • 子集后缀和主要是解决形如 c(S)=SQc(Q)c'(S)=\sum_{S\subset Q}c(Q) 问题的方法。
  • 其实就是改了一下 if 里的条件
1
2
3
4
5
for (int i = 0; i < n; ++i>) {
for (int j = 0; j < (1 << n); ++j) {
if (j&(1 << i) == 0) { c[j] += c[j ^ (1 << i)]; }
}
}
1
2
3
4
5
for (int i = 0; i < n; ++i>) {
for (int j = 0; j < (1 << n); ++j) {
if (j&(1 << i) == 0) { c[j] -= c[j ^ (1 << i)]; }
}
}

欢迎关注我的其它发布渠道