SOS dp(高维前缀dp)
有个数组\(A\)，求数组\(B\)
\(B[i]=\sum_{j|i=i} A[j]\)
数组\(A\)的下标从0到\(2^n\)
\(SOS dp\)可以在\(O(n2^n)\)算出来
代码
for (int i = 0; i < (1 << N); i++)B[i] = A[i];
for (int i = 0; i < N; i++)for (int j = (1 << N) - 1; j >= 0; j--)if (j & (1 << i))B[j] += B[j ^ (1 << i)];
也可以来求
\(B[i]=max\{A[j]\},i|j=i\)
for (int i = 0; i < (1 << N); i++)B[i] = A[i];
for (int i = 0; i < N; i++)for (int j = (1 << N) - 1; j >= 0; j--)if (j & (1 << i))B[j] = max(B[j], B[j ^ (1 << i)]);
或者
\(B[i]=\sum_{j|i=j} A[j]\)
for (int i = 0; i < (1 << N); i++)B[i] = A[i];
for (int i = 0; i < N; i++)for (int j = (1 << N) - 1; j >= 0; j--)if (!(j & (1 << i)))B[j] += B[j ^ (1 << i)];
例题我们需要更多的例题
Problem - F - Codeforces
求\(a[i]|(a[j]\&a[k]) 的最大值,i<j<k\)
容易得到\(a[i]|(a[j]\&a[k])=\bar{a[i]}\&a[j]\&a[k]+a[i]\)
让\(C[i]=i\)值出现得最早下标
那么我们可以算\(B[i]=\)该\(\{C[j]\},(i|j=j)\)集合里得最大值
\(D[i]=\)该\(\{C[j]\},(i|j=j)\)集合里得次大值
枚举\(a[i]\), 然后从高位枚举S（\((\bar{a[i]}\&a[j]\&a[k])|S=(\bar{a[i]}\&a[j]\&a[k])\)）, 看D[S]是否大于i，如果大于\(ans=max(s+a[i],ans)\)
代码
const int mod = 998244353, N = 1e7 + 10, G = 3;
ll a[N];
ll B[N];
ll D[N];
void add(int x, int id)
{if (id > B[x]){D[x] = B[x];B[x] = id;}else if (id >= D[x]){D[x] = id;}
}
void solve()
{int n;cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];add(a[i], i); // 初始话 B数组D数组}ll nx = 22;for (int i = 0; i < nx; i++) // sos dpfor (int j = (1 << nx) - 1; j >= 0; j--)if (!(j & (1 << i))){add(j, B[j ^ (1 << i)]);add(j, D[j ^ (1 << i)]);}ll ans = 0;for (int i = 1; i <= n; i++){int c = (1 << nx) - 1 - a[i]; // 枚举非a[i]int s = 0; // S=非a[i]&a[j]&a[k];for (int j = nx - 1; j >= 0; j--){if (!((c >> j) & 1)) // 非a[i]的第j位如果是0则continue，continue;s += (1 << j);if (D[s] < i){s -= (1 << j);}ans = max(ans, a[i] + s);}}cout << ans << endl;
}
P5495 【模板】Dirichlet 前缀和 - 洛谷 (luogu.com.cn))
根据前面的代码可知道。
for (枚举所有集合i)B[i] = A[i];
for (枚举元素i)for (枚举集合j)if (如果集合j包含元素i)B[j] = max(B[j], B[集合j去除掉元素i]);对于这个题我们可以把质数当作元素。
const int mod = 998244353, N = 2e7 + 10, G = 3;
int isVisit[N], prime[N], c = 0;
void EulerSevie(int n)
{for (int i = 2; i <= n; ++i) // 老规矩，遍历区间{if (isVisit[i] == false) // 如果这个数未被访问，则是素数prime[++c] = i; // 将素数保存在素数数组里面，计数+1// 下面for循环及里面的语句才是这个算法的精髓，我们下面细讲for (int j = 1; j <= c && i * prime[j] <= n; ++j){isVisit[i * prime[j]] = true;if (i % prime[j] == 0)break;}}
}
#define uint unsigned int
uint seed;
inline uint getnext()
{seed ^= seed << 13;seed ^= seed >> 17;seed ^= seed << 5;return seed;
}
uint b[N];
void solve()
{ll n;cin >> n >> seed;EulerSevie(n);for (int i = 1; i <= n; i++){b[i] = getnext();}for (uint i = 1; i <= c; i++){for (uint j = 1; prime[i] * j <= n; j++){b[prime[i] * j] += b[j];}}uint ans = 0;for (int i = 1; i <= n; i++){ans = ans ^ b[i];}cout << ans << endl;
}