【學習筆記】高維前綴和（SOSDP）
高維前綴和（SOSDP）解決這樣的問題：
給定 \(f_i\)，其中 \(i\in[0,2^n-1]\)，求解 \(\sum\limits_{j\subseteq i}f_j\)。
考慮一維前綴和：
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+a[i];
}
二維前綴和：
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
sum[i][j]=sum[i][j-1]+a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
sum[i][j]+=sum[i-1][j];
}
}
三維前綴和：
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
sum[i][j][k]=sum[i][j][k-1]+a[i][j][k];
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
sum[i][j][k]+=sum[i][j-1][k];
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
sum[i][j][k]+=sum[i-1][j][k];
}
}
}
可以發現上面那個問題就是每一維大小都為 \(2\) 的 \(n\) 維前綴和。
因此可以考慮枚舉每一維，然后再加上這一維的貢獻就好了。
這里分為兩種DP：子集和超集。
子集就是指子集。
for(int i=1;i<=n;i++){
for(int S=0;S<1<<n;S++){
if(S>>(i-1)&1){
continue;
}
f[S|1<<(i-1)]+=f[S];
}
}
自己是超集的子集。
換句話說，上面的問題的判斷條件為 \(i\subseteq j\) 時應使用超集。
因為是用大的更新小的，所以 \(S\) 要倒序枚舉。
Upd on 2024.12.27：似乎并不用倒序枚舉，因為對于每一維，每個 \(S\) 要么只增加要么只被增加，而且只會用一遍。因此不用考慮轉移順序。后面一道題的高維差分也是一樣的。
for(int i=1;i<=n;i++){
for(int S=(1<<n)-1;~S;S--){
if(S>>(i-1)&1){
f[S^1<<(i-1)]+=f[S];
}
}
}
CF 1234F
因為字符不重復，因此不用考慮它們的排列順序，即翻轉子串就是將兩個不交的子串連到一塊。這里不交既指位置不交又指字符集不交。但顯然字符集不交則一定位置不交。因此只用考慮對每一個字符集處理最大長度。高維前綴最大值即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e6+5,maxm=(1<<20)+5;
int n,dp[maxm];
char s[maxn];
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
scanf(" %s",s+1);
n=strlen(s+1);
for(int i=1;i<=n;i++){
for(int j=i,S=0;j;j--){
if(S>>(s[j]-'a')&1){
break;
}
S|=1<<(s[j]-'a');
dp[S]=i-j+1;
}
}
for(int i=1;i<=20;i++){
for(int S=0;S<1<<20;S++){
if(S>>(i-1)&1){
continue;
}
dp[S|1<<(i-1)]=max(dp[S|1<<(i-1)],dp[S]);
}
}
int ans=0;
for(int S=1;S<=(1<<20)-2;S++){
ans=max(ans,dp[S]+dp[((1<<20)-1)^S]);
}
printf("%d",ans);
return 0;
}
}
int main(){return asbt::main();}
CF 165E
\(a_i\le 4\times 10^6\)，也就是說 \(a\) 的全集為 \(2^{22}\)?？紤]答案就是 \(a_i\) 的補集的某個子集。SOSDP將 \(a\) 值不斷上傳即可。注意代碼中選擇了取 \(\max\)，目的是避免被 \(0\) 更新。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e6+5,maxm=(1<<22)+5;
int n,a[maxn],f[maxm];
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n);
for(int i=1;i<=n;i++){
read(a[i]);
f[a[i]]=a[i];
}
for(int i=1;i<=22;i++){
for(int S=0;S<1<<22;S++){
if(S>>(i-1)&1){
continue;
}
int nS=S|1<<(i-1);
f[nS]=max(f[nS],f[S]);
}
}
for(int i=1;i<=n;i++){
int tmp=((1<<22)-1)^a[i];
printf("%d ",f[tmp]?f[tmp]:-1);
}
return 0;
}
}
int main(){return asbt::main();}
AT arc100C
考慮對每個 \(k\)，算出 \(i\mid j\subseteq k\) 的答案，然后再對 \(k\) 進行前綴最大值即可?？紤]若 \(i\mid j\subseteq k\)，則一定滿足 \(i\subseteq k\)，\(j\subseteq k\)。因此高維前綴最大值、次大值即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=(1<<18)+5;
int n,f[maxn],g[maxn],hp[7],ans[maxn];
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n);
for(int i=0;i<1<<n;i++){
read(f[i]);
}
for(int i=1;i<=n;i++){
for(int S=0;S<1<<n;S++){
if(S>>(i-1)&1){
continue;
}
int nS=S|1<<(i-1);
hp[1]=f[S],hp[2]=g[S];
hp[3]=f[nS],hp[4]=g[nS];
sort(hp+1,hp+5);
f[nS]=hp[4],g[nS]=hp[3];
}
}
for(int i=1;i<1<<n;i++){
ans[i]=max(ans[i-1],f[i]+g[i]);
printf("%d\n",ans[i]);
}
return 0;
}
}
int main(){return asbt::main();}
CF 1208F
首先，\(a_i\mid(a_j\& a_k)=((\complement_Ua_i)\&a_j\&a_k)+a_i\)。
二進制數最大，我們考慮按位貪心。枚舉到 \(i\) 時，若要這一位為 \(1\)，則必須滿足至少有兩個 \(a\) 值的這一位為 \(1\)，且下標必須大于 \(i\)。SOSDP維護超集的最大與次大位置即可。
\(i\) 的枚舉只能到 \(n-2\)，因為 \(i=n-1\) 或 \(n\) 時 \(((\complement_Ua_i)\&a_j\&a_k)\) 這一部分會被算成 \(0\)，答案會被 \(a_i\) 直接更新。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e6+5;
const int maxm=(1<<21)+5,uS=(1<<21)-1;
int n,a[maxn],f[maxm],g[maxm],hp[10];
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n);
for(int i=1;i<=n;i++){
read(a[i]);
hp[1]=f[a[i]];
hp[2]=g[a[i]];
hp[3]=i;
sort(hp+1,hp+4);
f[a[i]]=hp[3];
g[a[i]]=hp[2];
}
for(int i=1;i<=21;i++){
for(int S=uS;~S;S--){
if(S>>(i-1)&1){
int nS=S^1<<(i-1);
hp[1]=f[S],hp[2]=g[S];
hp[3]=f[nS],hp[4]=g[nS];
sort(hp+1,hp+5);
f[nS]=hp[4],g[nS]=hp[3];
}
}
}
// for(int i=0;i<=15;i++){
// cout<<f[i]<<" "<<g[i]<<"\n";
// }
int ans=0;
for(int i=1;i<=n-2;i++){
int nS=uS^a[i],res=0;
// cout<<i<<"\n";
for(int j=21;~j;j--){
// cout<<" "<<j<<"\n";
if(nS>>j&1){
res|=1<<j;
if(g[res]<=i){
res^=1<<j;
}
}
}
ans=max(ans,a[i]+res);
}
printf("%d",ans);
return 0;
}
}
int main(){return asbt::main();}
/*
3
1 5 15
*/
CF 383E
考慮單詞不合法，即每一個字母都不是元音。
對每個單詞狀壓，然后高維前綴和計算每一個字符集包含的單詞數量，最后枚舉元音的補集統計答案。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=(1<<24)+5;
int n,f[maxn];
char s[10];
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n);
for(int i=1,S;i<=n;i++){
scanf(" %s",s+1);
S=0;
for(int j=1;j<=3;j++){
S|=1<<(s[j]-'a');
}
f[S]++;
}
for(int i=1;i<=24;i++){
for(int S=0,nS;S<1<<24;S++){
if(S>>(i-1)&1){
continue;
}
nS=S|1<<(i-1);
f[nS]+=f[S];
}
}
int ans=0;
for(int i=0;i<1<<24;i++){
ans^=(n-f[i])*(n-f[i]);
}
printf("%d",ans);
return 0;
}
}
int main(){return asbt::main();}
CodeChef COVERING
令 \(f_S=\sum\limits_{i\mid j\mid k=S}a_ib_jc_k\)，則不難發現答案即為 \(\sum f_S\times 2^{|S|}\)。
考慮如何求解 \(f\)，不難想到令 \(A_S\)，\(B_S\)，\(C_S\) 為 \(\sum\limits_{i\subseteq S}a_i\)，\(\sum\limits_{i\subseteq S}b_i\)，\(\sum\limits_{i\subseteq S}c_i\)，則有：
\[f_S=A_SB_SC_S-\sum_{i\subsetneqq S}f_i
\]
移項得：
\[A_SB_SC_S=\sum_{i\subseteq S}f_i
\]
高維差分即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define popcnt __builtin_popcount
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=(1<<20)+5,mod=1e9+7;
int n,f[maxn];
int a[maxn],b[maxn],c[maxn];
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n);
for(int i=0;i<1<<n;i++){
read(a[i]);
}
for(int i=0;i<1<<n;i++){
read(b[i]);
}
for(int i=0;i<1<<n;i++){
read(c[i]);
}
for(int i=1;i<=n;i++){
for(int S=0,nS;S<1<<n;S++){
if(S>>(i-1)&1){
continue;
}
nS=S|1<<(i-1);
(a[nS]+=a[S])%=mod;
(b[nS]+=b[S])%=mod;
(c[nS]+=c[S])%=mod;
}
}
for(int i=0;i<1<<n;i++){
f[i]=a[i]*1ll*b[i]%mod*c[i]%mod;
}
for(int i=1;i<=n;i++){
for(int S=0;S<1<<n;S++){
if(S>>(i-1)&1){
continue;
}
(f[S|1<<(i-1)]+=mod-f[S])%=mod;
}
}
int ans=0;
for(int i=0;i<1<<n;i++){
(ans+=f[i]*(1ll<<popcnt(i))%mod)%=mod;
}
printf("%d",ans);
return 0;
}
}
int main(){return asbt::main();}
浙公網安備 33010602011771號