自动搬运

查看原文

来自洛谷，原作者为

	DaiRuiChen007 白鸟白鸟 不要回头望 你要替我飞去那地方 一去那地方 那是你我共同故乡

搬运于2025-08-24 23:15:58，当前版本为作者最后更新于2025-06-09 22:54:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Problem Link

题目大意

给定 $s_1\sim s_{n-1}$，其中每个元素都是 $\mathrm{AND},\mathrm{OR},\oplus$ 三种运算符之一，$q$ 次询问 $m$。

求有多少 $c_1\sim c_n\in [0,2^k)$ 并且存在 $a_1\sim a_n$ 满足 $a_i\in[0,c_i]$ 且 $((a_1 \otimes_{s_1}a_2)\otimes_{s_2}a_3\cdots)\otimes_{s_{n-1}}a_n=m$。

答案对 $2^{32}$ 取模。

数据范围：$n,q\le 1000,k\le 30$。

思路分析

考虑如何检验一组 $c$。

打表发现能表示出的 $m$ 一定是一段前缀 $[0,x]$，下面给出归纳证明：

• $s_i=\mathrm{AND}$：则 $x\gets \min(x,c)$。
• $s_i=\mathrm{OR}$：则 $x\gets x\operatorname{OR}c\operatorname{OR}(\mathrm{highbit}(x\operatorname{AND}c)-1)$。
• $s_i=\oplus$：可以通过 $a\gets a-(a\operatorname{AND} x)$ 转成 $s_i=\mathrm{OR}$ 的情况。

那么我们只要考虑操作为 $\mathrm{AND}$ 或 $\mathrm{OR}$ 的情况。

但是正着依然不好维护判定过程考虑再倒过来，此时我们只要贪心让要得出的 $x$ 尽可能小即可。

• $s_i=\mathrm{AND}$：则 $c_i\ge x$ 即可，$x$ 显然不变最优，方案数 $2^k-x$。

• $s_i=\mathrm{OR}$：很显然最优的情况下更新后的 $x',c$ 无交，否则把 $2^k=\mathrm{highbit}(x'\operatorname{AND}c)$ 变成 $2^0+\cdots+2^{k-1}$ 更优。

  因此只要 $x'\operatorname{OR}c\ge x$ 即可，从高到低考虑，如果这一位上 $c=0$ 则不更新，如果这一位 $c=1,x=1$ 则 $x$ 这一位变成 $0$，否则低位全部清空。

  更具体一点，我们找到 $x$ 不包含的一个位 $2^p$，然后把低 $p$ 位清零，系数 $2^p$（$c$ 的低位填法），然后每个 $>p$ 的位上的 $1$ 可以选择是否变成 $0$。

那么对这个过程 dp，但这次从前往后 dp。

对于 $s_i=\mathrm{AND}$ 的位置，我们很难在不知道 $x$ 的情况下算方案数 $2^k-x$。

可以把 $x$ 拆成二进制 $2^{t_1}+\cdots+2^{t_q}$，然后枚举每个 $2^{t_i}\in x$，系数为 $-2^{t_i}$，或者不枚举，系数为 $2^k$。

因此对于每个 $s_i=\mathrm{AND}$ 的位置，我们可以选择直接 $\times 2^k$，或选择一个 $v$，钦定此时 $2^v\in x$，系数为 $-2^v$。

那么我们从前往后，会确定若干个位置必定属于 $x$。

然后考虑对 $s_i=\mathrm{OR}$ 的影响，找到此前被钦定的所有位置中最小的一个 $d$，选择的那么 $p<d$。

并且在这个位置，我们具体选择哪个 $p$ 没有影响，因为再往前的所有方案数的计算都不关心 $<d$ 的位的任何值，所以方案数就是任填的 $2^d$。

那么动态维护从前往后 $d$ 的轮廓线，此时还有一些没确定的决策，也就就是 $s_i=\mathrm{OR}$ 的时候 $>d$ 的位可以选择从 $1$ 变成 $0$。

对于每个位，考虑他从前往后首次被钦定为 $1$ 的时刻 $t_r$，以及其首次高于轮廓线的时刻 $t_l$，则 $[t_l,t_r]$ 中任意一个 $\mathrm{OR}$ 操作都可以把这个位从 $1$ 变成 $0$，系数就是这一段的 $\mathrm{OR}$ 个数。

注意到转移系数大部分都是 $2$ 的幂，而模数又是 $2^{32}$，所以很多转移最后在模意义下系数为 $0$。

考虑这样刻画轮廓线：$c_0\sim c_{k-1}$，其中 $c_i>1$ 表示 $d=i$ 时的 $\mathrm{OR}$ 操作次数为 $c_i-1$，$c_i=1$ 表示已存在一个 $\mathrm{AND}$ 操作钦定了这个位，否则表示不存在。

容易发现系数一定是 $2^{\sum i\times c_i}$ 的倍数，钦定 $c_0\in\{0,1\}$，则状态数是拆分数级别的。

查询答案的时候暴力枚举每个合法的状态即可。

时间复杂度 $\mathcal O((n+q)k|S|)$，其中 $|S|$ 为状态数，$|S|\le 7.2\times 10^4$。

代码呈现

#include<bits/stdc++.h>
#define ui unsigned
#define ull unsigned long long
using namespace std;
const int MAXN=1005,MAXM=72005,MAXE=2e6+5;
typedef array<int,32> info;
int n,k,m,q,op[MAXN],lo[MAXM],vl[MAXM][32];
info st[MAXM],s;
mt19937_64 rnd(time(0));
ull wt[32],hs[MAXM];
const int P=1e7+19;
int hd[P],nxt[MAXM],msk[MAXM];
int qry(ull x) {
	for(int i=hd[x%P];i;i=nxt[i]) if(hs[i]==x) return i;
	return 0;
}
void dfs(int i,int c) {
	if(i>k) {
		++s[k],st[++m]=s;
		for(int j=0;j<=k;++j) hs[m]+=s[j]*wt[j];
		nxt[m]=hd[hs[m]%P],hd[hs[m]%P]=m,--s[k];
		return ;
	}
	for(s[i]=0;s[i]*i<=c;++s[i]) dfs(i+1,c-i*s[i]);
}
int to[MAXM][2],R[MAXE],Z[MAXE],e,h[MAXM];
ui pr[MAXM][2],f[MAXM],g[MAXM];
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>k>>q;
	for(int i=0;i<=k;++i) wt[i]=rnd();
	s.fill(0),dfs(1,31),s.fill(0),s[0]=1,dfs(1,31);
	for(int i=2;i<=n;++i) { char c; cin>>c,op[i]=(c!='A'); }
	for(int i=1;i<=m;++i) {
		int &p=lo[i]=0;
		for(;!st[i][p];++p);
		to[i][1]=qry(p?hs[i]+wt[p]:hs[i]),pr[i][1]=1u<<p;
		to[i][0]=i,pr[i][0]=1u<<k;
		for(int j=0;j<k;++j) {
			if(st[i][j]) pr[i][0]-=1u<<j,msk[i]|=1<<j;
			else R[++e]=qry(hs[i]+wt[j]),Z[e]=j;
		}
		h[i]=e;
		for(int j=k;~j;--j) vl[i][j]=vl[i][j+1]+max(0,st[i][j]-1);
	}
	f[qry(wt[k])]=1;
	int ct=0;
	for(int o=1;o<=n;++o) {
		memset(g,0,sizeof(g)),ct+=op[o];
		for(int i=1;i<=m;++i) if(f[i]) {
			g[to[i][op[o]]]+=f[i]*pr[i][op[o]];
			if(!op[o]) for(int j=h[i-1]+1;j<=h[i];++j) {
				if(Z[j]<lo[i]) g[R[j]]-=f[i]<<Z[j];
				else g[R[j]]-=f[i]*(ct-vl[i][Z[j]]+1)<<Z[j];
			}
		}
		memcpy(f,g,sizeof(f));
	}
	for(int x;q--;) {
		cin>>x; ui z=0;
		for(int i=1;i<=m;++i) if((x|msk[i])==x) {
			ui t=f[i];
			for(int j=0;j<k;++j) if((x>>j&1)&&!st[i][j]) t*=ct-vl[i][j]+1;
			z+=t;
		}
		cout<<z<<"\n";
	}
	return 0;
}