「JOI 2018 Final」毒蛇越狱

Posted on Edited on In

「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(Q\cdot 2^k)\)

对于剩下的 \(n-k\) 个位置，采取上面的暴力方法预处理，三进制枚举，预处理复杂度为 \(O(2^k3^{n-k})\)

因此复杂度为 \(O(Q\cdot 2^k +2^k3^{n-k})\) ，计算在 \(k=6,7\) 时复杂度约为 \(3.5\cdot 10^8\)

(这是一个非常稳的复杂度)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#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\n",Ans[i]);
}

Algorithm 3 : 高位前缀和+容斥

起始学过高位前缀和/FMT的看到这个题第一反应可能都是这个。。

-> 对于 \(?\) 的位置，直接赋值成1，然后对于这个数从高位前缀和里查询

然后你发现不知道怎么对于1的把0的去掉

显然这个可以通过一个暴力的容斥来完成，枚举一些1的位置变成0，然后就是容斥的奇数减偶数加

复杂度为 \(O(Q\cdot 2^{1的个数}\ \ \ \ \ )\)

同理，处理高位后缀和，复杂度为 \(\begin{aligned}O(Q\cdot 2^{0的个数}\ \ \ \ )\end{aligned}\)

而直接暴力枚举 \(?\) 变成0/1，复杂度为 \(\begin{aligned}O(Q\cdot 2^{?的个数}\ \ \ \ \ )\end{aligned}\)

综合这三种算法，选一个更优的做，就得到一个复杂度为

\(\begin{aligned}O(Q \ \cdot 2^{ \begin{aligned}\ \ \ \ \ \ \ \ \ \ \min\lbrace 1的个数,0的个数,?的个数\rbrace\end{aligned}})\ \ \ \ \ \ \end{aligned}\)

显然查询复杂度就是 \(O(Q\cdot 2^{\lfloor \frac{n}{3}\rfloor }=Q\cdot 2^6)\)

算上预处理，复杂度为 \(O(2^nn+Q\cdot 2^6)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#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\n",ans);
	}
}