题解：CF1728G Illumination

· · 题解

貌似是容易的，注意到坐标轴区间为 [0,d]，那说明不管我们之前怎么亮灯，只要一个点就能救回来所有点。

假设现在只有一个在 p 处的灯没有分配，左边最后一个没有被覆盖的点距离为 x，右边最后一个为 y（不存在则为 0）。

那最后的贡献显然是 d-\max(x,y)+1。

预处理出 f_S 表示恰好只有 S 内的点没被覆盖的方案数，可以设 g_S 表示钦定 S 内的点没亮，然后对 g 高维后缀差分得到 f_S。g_S 可以 O(2^mm+nm^2) 完成。

随便做到更优秀只是这样好写一点。

然后再处理出 p_{x,y} 表示最左边没覆盖的点为 x，右边为 y 的方案数，显然 O(2^mm) 可以处理。

然后加入一个灯的时候可以通过 p_{x,y} 暴力更新。

贡献来自三部分：

  1. 不需要新灯就合法的方案。
  2. 所有没覆盖的点都在一边的方案。
  3. 左右都有的方案。

第二部分和第三部分可以放到一起算，随便做就好了，是 O(qm^2) 的样子，常数很小（存疑）。

#include<bits/stdc++.h>

using namespace std;

const int mod=998244353,N=5e5+10,inf=1e9;
struct modint {
    int val;
    static int norm(const int& x) { return x < 0 ? x + mod : x; }
    modint inv() const {
        int a = val, b = mod, u = 1, v = 0, t;
        while (b > 0) t = a / b, swap(a -= t * b, b), swap(u -= t * v, v);
        return modint(u);
    }
    modint() : val(0) {}
    modint(const int& m) : val(norm(m)) {}
    modint(const long long& m) : val(norm(m % mod)) {}
    modint operator-() const { return modint(norm(-val)); }
    modint& operator+=(const modint& o) { return val = (1ll * val + o.val) % mod, *this; }
    modint& operator-=(const modint& o) { return val = norm(1ll * val - o.val), *this; }
    modint& operator*=(const modint& o) { return val = static_cast<int>(1ll * val * o.val % mod), *this; }
    modint operator-(const modint& o) const { return modint(*this) -= o; }
    modint operator+(const modint& o) const { return modint(*this) += o; }
    modint operator*(const modint& o) const { return modint(*this) *= o; }
    friend std::ostream& operator<<(std::ostream& os, const modint& a) { return os << a.val; }
}g[N],p[21][21],s[21][21],ans,res;
int d,n,m,q,a[N],b[N],c[N];

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>d>>n>>m;for(int i=1;i<=n;++i) cin>>a[i];
    for(int i=1;i<=m;++i) cin>>b[i];
    cin>>q;for(int i=1;i<=q;++i) cin>>c[i];
    sort(a+1,a+1+n);sort(b+1,b+1+m);b[0]=-inf;b[m+1]=inf;
    for(int i=0;i<=m;++i){
        for(int j=i+1;j<=m+1;++j){
            int x=b[i],y=b[j];s[i][j]=1;
            for(int k=1;k<=n;++k){
                if(a[k]<x||a[k]>y) continue;
                s[i][j]*=min(min(a[k]-x,y-a[k]),d+1);
            }
        }
    }
    for(int S=0;S<(1<<m);++S){
        int las=0;modint res=1;
        for(int i=1;i<=m;++i){
            if((S>>(i-1))&1){
                res*=s[las][i];las=i;
            }
        }
        res*=s[las][m+1];g[S]=res;
    }
    for(int i=0;i<m;++i) for(int S=0;S<(1<<m);++S) if((S>>i)&1) g[S^(1<<i)]-=g[S];
    ans=g[0];
    for(int i=1;i<(1<<m);++i){
        int lef=0,rig=0;
        for(int j=0;j<m;++j) if((i>>j)&1) rig=j+1;
        for(int j=m-1;~j;--j) if((i>>j)&1) lef=j+1;
        p[lef][rig]+=g[i];
    }
    for(int i=1;i<=q;++i){
        int pos=c[i];modint res=ans*(d+1);
        for(int i=1;i<=m;++i){
            for(int j=i;j<=m;++j){
                int dis=max(abs(pos-b[i]),abs(pos-b[j]));
                res+=p[i][j]*(d-dis+1);
            }
        }
        cout<<res<<'\n';
    }
    return 0;
}