「JOI 2018 Final」毒蛇越狱
Algorithm 1: 暴力计算
对于所有(0,1,?)组成的(3^n)种串处理出答案
具体的，对于当前串包含的最后一个(?)位置，枚举它变成0/1的答案，按照一定的顺序累和即可
(代码可以在Algo2里面看到)
Algorithm 2 : Meet in the Middle
(3^{20})太大，优化上面的暴力，容易想到把复杂度从预处理分一部分给查询
取出(n)中前(k)个位置，这些位置不处理(3^k)，而是让每个询问暴力地去枚举这些位置上的(?)变成(0/1)
显然每个询问有最多(2^k)次枚举，即复杂度为(O(Qcdot 2^k))
对于剩下的(n-k)个位置，采取上面的暴力方法预处理，三进制枚举，预处理复杂度为(O(2^k3^{n-k}))
因此复杂度为(O(Qcdot 2^k +2^k3^{n-k}))，计算在(k=6,7)时复杂度约为(3.5cdot 10^8)
(这是一个非常稳的复杂度)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
#define reg register
#define pb push_back
#define mp make_pair
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }
char IO;
ll rd(){
ll s=0,f=0;
while(!isdigit(IO=getchar())) if(IO=='-') f=1;
do s=(s<<1)+(s<<3)+(IO^'0');
while(isdigit(IO=getchar()));
return f?-s:s;
}
const int N=20,M=1<<20,M3=1600000;
const int DM=7;
int n,m,k;
int Pow[N],S[M3],Low[M3],trans[M3];
int QX[M],QY[M],QZ[M],Ans[M],rev[M];
char val[M],q[N];
int main() {
rep(i,Pow[0]=1,N-1) Pow[i]=Pow[i-1]*3;
n=rd(),m=rd(),k=min(DM,n),scanf("%s",val);
rep(i,1,(1<<n)-1) {
rev[i]=(rev[i>>1]>>1)|((i&1)<<(n-1));
if(i<rev[i]) swap(val[i],val[rev[i]]);
}
Low[0]=1e9;
rep(i,1,Pow[n-k]-1) {
Low[i]=(i%3==2)?0:Low[i/3]+1;
if(Low[i]>n) trans[i]=(trans[i/3]<<1)|(i%3);
}
rep(i,1,m) {
scanf("%s",q);
rep(j,0,n-1) {
if(q[j]=='?') QY[i]|=1<<j,q[j]='2';
else QX[i]|=(q[j]-'0')<<j;
}
rep(j,k,n-1) QZ[i]+=Pow[j-k]*(q[j]-'0');
}
int A=(1<<k)-1;
rep(i,0,A) {
rep(j,0,Pow[n-k]-1) {
if(Low[j]>n) S[j]=val[(trans[j]<<k)|i]-'0';
else S[j]=S[j-Pow[Low[j]]]+S[j-2*Pow[Low[j]]];
} // 暴力预处理前缀和
rep(j,1,m) if((QX[j]&A)==(i&~QY[j])) Ans[j]+=S[QZ[j]];
}
rep(i,1,m) printf("%d
",Ans[i]);
}
Algorithm 3 : 高位前缀和+容斥
起始学过高位前缀和/FMT的看到这个题第一反应可能都是这个。。
-> 对于(?)的位置，直接赋值成1，然后对于这个数从高位前缀和里查询
然后你发现不知道怎么对于1的把0的去掉
显然这个可以通过一个暴力的容斥来完成，枚举一些1的位置变成0，然后就是容斥的奇数减偶数加
复杂度为(O(Qcdot 2^{1的个数} ))
同理，处理高位后缀和，复杂度为(egin{aligned}O(Qcdot 2^{0的个数} )end{aligned})
而直接暴力枚举(?)变成0/1，复杂度为(egin{aligned}O(Qcdot 2^{?的个数} )end{aligned})
综合这三种算法，选一个更优的做，就得到一个复杂度为
(egin{aligned}O(Q cdot 2^{ egin{aligned} minlbrace 1的个数,0的个数,?的个数 braceend{aligned}}) end{aligned})
显然查询复杂度就是(O(Qcdot 2^{lfloor frac{n}{3} floor }=Qcdot 2^6))
算上预处理，复杂度为(O(2^nn+Qcdot 2^6))
#include<bits/stdc++.h>
using namespace std;
enum{N=1<<20};
int n,k,m,A[N],B[N],C[N],P[N];
// A 高位前缀和
// B 高位后缀和
// C 点值(打扰了)
// P __builtin_parity
char val[N],q[21];
int main() {
scanf("%d%d%s",&n,&m,val),k=1<<n;
for(int i=0;i<k;++i) A[i]=B[i]=C[i]=val[i]-'0',P[i]=P[i>>1]^(i&1);
for(int i=1;i<k;i<<=1) for(int l=0;l<k;l+=i*2) for(int j=l;j<l+i;++j) A[j+i]+=A[j],B[j]+=B[j+i];
//预处理高位前缀和，高位后缀和
while(m--) {
int x=0,y=0,a=0,b=0,ans=0;
for(int i=scanf("%s",q+1);i<=n;++i) {
if(q[i]=='?') x|=1<<(n-i),a++;
if(q[i]=='1') y|=1<<(n-i),b++;
}
if(a<=n/3) for(int S=x;~S;S=S?(S-1)&x:-1) ans+=C[y|S]; // 枚举?变成0/1
else if(b<=n/3) for(int S=y;~S;S=S?(S-1)&y:-1) ans+=P[S^y]?-A[S|x]:A[S|x]; // 对于高位前缀和容斥
else for(int S=x=(k-1)^x^y;~S;S=S?(S-1)&x:-1) ans+=P[S]?-B[S|y]:B[S|y]; // 对于高位后缀和容斥
printf("%d
",ans);
}
}