题解：CF1728G Illumination

· · 题解

\text{Link}

先考虑除了询问那个点以外其它点的贡献。

考虑把 n 个点的贡献刻画成哈集幂集合幂级数的形式，把乘法定义成或卷积，令第 i 个点的集合幂级数为 F_i，则我们要求的是 \prod_{i=1}^n F_i。

注意到 m 非常小，所以 F_i 中只会有 O(m) 个位置有值，并且我们在求 F_i 的时候是按距离把 m 个点依次加入的，所以每次新加入的集合都是之前集合的超集。

考虑把有值的位置相同的那些 F_i 弄到一起做，一共只有 O(m^2) 种（考虑从左到右移动灯笼，新增一种就是交换了相邻的两个点，显然一个点对只会被交换一次）。

对于同一种，因为每次新加入的集合都是之前集合的超集，只要把所有有值的位置扫一遍就可以得出两者的或卷积。

处理完每一种的贡献之后，把不同种类用 FWT 求或卷积，设 \prod_{i=1}^n F_i=G。

现在考虑对于一个询问，新加入的这个灯笼的集合幂级数也只有 O(m) 个位置有值，称它为 H，全集为 U，我们要求的是 [x^U]GH，枚举 H 的所有有值的系数，如果或卷积之后得到的是 U，我们就要选它补集的超集，预处理 G 的高维后缀和即可。

时间复杂度 O((n+q)m\log m+m^22^m)。

::::info[Code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
const int N=5e5+10,mod=998244353;
inline int add(int a,int b){return ((a+=b)>=mod)?(a-mod):a;}
inline int norm(int a,int b){return ((a-=b)<0)?(a+mod):a;}
int d,n,m,qwq,a[N],p[30],id[30],val[N],s[N],cnt;
mt19937_64 rnd(time(0));
const ull pp=13331;
ull pri[(1<<16)+5];
map<ull,int>mp;
vector<int>f[270];
inline void fwt_OR(vector<int>&f,int opt){
    int limit=f.size();
    for(int len=2;len<=limit;len<<=1)
    for(int i=0;i+len-1<limit;i+=len)
    for(int j=i+(len>>1);j<i+len;++j)
      f[j]=add(f[j],f[j-(len>>1)]*opt%mod);
}
inline void fwt_AND(vector<int>&f){
    int limit=f.size();
    for(int len=2;len<=limit;len<<=1)
    for(int i=0;i+len-1<limit;i+=len)
    for(int j=i;j<i+(len>>1);++j)
      f[j]=add(f[j],f[j+(len>>1)]);
}
signed main(){
    cin>>d>>n>>m;
    for(int i=0;i<(1<<m);++i)pri[i]=rnd();
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=1;i<=m;++i){
      cin>>p[i];
      id[i]=i;
    }
    for(int i=1;i<=n;++i){
      sort(id+1,id+1+m,[&](int x,int y){return abs(a[i]-p[x])<abs(a[i]-p[y]);});
      val[0]=abs(a[i]-p[id[1]]),s[0]=0;
      ull hash=0;
      for(int j=1;j<=m;++j){
        s[j]=s[j-1]|(1<<(id[j]-1));
        hash=hash*pp+pri[s[j]];
        if(j==m)val[j]=d-abs(a[i]-p[id[j]])+1;
        else val[j]=abs(a[i]-p[id[j+1]])-abs(a[i]-p[id[j]]);
      }
      if(mp.find(hash)==mp.end()){
        mp[hash]=++cnt;
        f[cnt].resize(1<<m);
        f[cnt][0]=1;
      }
      int sum1=0,sum2=0,pos=mp[hash];
      for(int j=0;j<=m;++j){
        int last=f[pos][s[j]];
        f[pos][s[j]]=add(last*sum2%mod,add(sum1*val[j]%mod,last*val[j]%mod));
        sum1=add(sum1,last);
        sum2=add(sum2,val[j]);
      }
    }
    int limit=(1<<m);
    f[0].resize(limit);
    for(int i=0;i<limit;++i)f[0][i]=1;
    for(int i=1;i<=cnt;++i){
      fwt_OR(f[i],1);
      for(int j=0;j<limit;++j)
        f[0][j]=f[0][j]*f[i][j]%mod;
    }
    fwt_OR(f[0],mod-1);
    fwt_AND(f[0]);
    cin>>qwq;
    int pos;
    while(qwq--){
      cin>>pos;
      sort(id+1,id+1+m,[&](int x,int y){return abs(pos-p[x])<abs(pos-p[y]);});
      val[0]=abs(pos-p[id[1]]),s[0]=0;
      for(int j=1;j<=m;++j){
        s[j]=s[j-1]|(1<<(id[j]-1));
        if(j==m)val[j]=d-abs(pos-p[id[j]])+1;
        else val[j]=abs(pos-p[id[j+1]])-abs(pos-p[id[j]]);
      }
      int ans=0;
      for(int i=0;i<=m;++i)ans=add(ans,val[i]*f[0][(limit-1)^s[i]]%mod);
      cout<<ans<<"\n";
    }
    return 0;
}

::::