P12494 题解

· · 题解

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]，下面给出归纳证明：

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

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

那么对这个过程 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;
}