题解：AT_ndpc2026_q 区間の和集合

· · 题解

更好的阅读体验

官解怎么是，拉插优化一坨东西，已吓哭。

然而并不需要，只要最基础的容斥 /qiang

题目就是，给你一堆区间，对于每个 x，求出从这些区间中选出若干个，并集大小恰好是 x 的方案数。

那么首先简单转换一下，变成未被覆盖的区域大小恰好是 \boldsymbol{m-x} 的方案数。

那么可以容斥。假设 S 是 [1, m] \cap \N 的一个子集，f_S 表示钦定集合 S 中的位置没被覆盖，其余格子无限制，的方案数。那么假设 |S| = k，S 中元素升序排序后是 S_1, S_2, \cdots, S_k。那么被完全包含于 [1, S_1), (S_1, S_2), (S_2, S_3) \cdots, (S_k, m] 的区间都可以随便选，而跨过 S 中任何一个元素的区间都不能选。因此假设不跨过 S 中任何一个元素的区间个数为 c，那么 f_S = 2^c。

那么我们考虑计算 F_k 表示 \sum \limits_{|S|=k} f_S。则可以设计一个 dp。假设 h_{i, j} 表示只考虑数轴上 \boldsymbol{[1, i]} 的点，目前 |S| = j 的 f_S 之和，且规定 i \isin S。假设 c_{l, r} 表示有多少个区间被完全包含于区间 [l, r]。我们可以枚举 S 中前一个选的点，那么有转移

\begin{gather} h_{i, j} = \sum_{k=0}^{i-1} h_{k, j-1} \cdot 2^{c_{k+1,i-1}} \nonumber \\ h_{0, 0} = 1 \nonumber \end{gather}

容易发现转移所需要的 c_{k+1, i-1} 一项是一个二维偏序的形式，这启发我们可以数据结构优化。具体地，我们可以维护每一个 k 会给当前 h_{i, j} 带来多少贡献（初始时就是 h_{k, j-1}）。假设我们现在位于 i，则我们枚举所有以 i 为右端点的区间 [l, i]，加入这个区间之后所有 k \isin [1, l) 的 k 带来的贡献都会 \times 2。

这是一个区间乘法求区间和的问题，线段树维护即可。然后由于 h 的转移只需要 j 和 j-1，可以滚动数组优化做到线性空间。

很显然我们可以利用 h 的 dp 值求出 F。则假设 G_k 表示恰好 k 个格子没被覆盖的的方案数，G 可以通过对 F 施加二项式反演求得。那么 G_{m-i} 就是 i 处的答案。

假设 n, m 同阶，时间复杂度为 O(n^2 \log n)，空间复杂度 O(n)。

#include<bits/stdc++.h>
#define endl '\n'
#define N 4006
#define MOD 998244353
using namespace std;
inline void add(int &x,int y) {x+=y,x-=x>=MOD?MOD:0;}
inline void dec(int &x,int y) {x+=MOD-y,x-=x>=MOD?MOD:0;}
inline void mul(int &x,int y) {x=1ll*x*y%MOD;}
int n,m,fac[N],ifac[N],pw2[N],old_f[N],f[N],cnt[N],g[N],h[N];
vector<int> vec[N];
struct Segtree {
    int tree[N<<2],tag[N<<2];
    void build(int p,int l,int r)
    {
        tag[p]=1;
        if(l==r)return tree[p]=old_f[l],(void)0;
        int mid=l+r>>1;
        build(p<<1,l,mid),build(p<<1|1,mid+1,r);
        tree[p]=(tree[p<<1]+tree[p<<1|1])%MOD;
    }
    inline void addtag(int p,int x) {mul(tree[p],x),mul(tag[p],x);}
    inline void push_down(int p) {addtag(p<<1,tag[p]),addtag(p<<1|1,tag[p]),tag[p]=1;}
    void update(int p,int l,int r,int L,int R,int x)
    {
        if(L<=l&&r<=R)return addtag(p,x);
        push_down(p); int mid=l+r>>1;
        if(L<=mid)update(p<<1,l,mid,L,R,x);
        if(R>mid)update(p<<1|1,mid+1,r,L,R,x);
        tree[p]=(tree[p<<1]+tree[p<<1|1])%MOD;
    }
    int query(int p,int l,int r,int L,int R)
    {
        if(L<=l&&r<=R)return tree[p];
        push_down(p); int mid=l+r>>1,ret=0;
        if(L<=mid)add(ret,query(p<<1,l,mid,L,R));
        if(R>mid)add(ret,query(p<<1|1,mid+1,r,L,R));
        return ret;
    }
} T;
main()
{
    scanf("%d%d",&n,&m),pw2[0]=fac[0]=1;
    for(int i=1;i<N;i++)
        pw2[i]=2ll*pw2[i-1]%MOD,fac[i]=1ll*i*fac[i-1]%MOD;
    auto qpow=[](int x,int y=MOD-2) {
        int ret=1;
        for(;y;y>>=1,x=1ll*x*x%MOD)if(y&1)ret=1ll*ret*x%MOD;
        return ret;
    };
    ifac[N-1]=qpow(fac[N-1]);
    for(int i=N-2;~i;i--)ifac[i]=1ll*ifac[i+1]*(i+1)%MOD;
    auto binom=[](int x,int y) {
        return (x<y||x<0||y<0)?0:1ll*fac[x]*ifac[y]%MOD*ifac[x-y]%MOD;
    };
    for(int i=1,l,r;i<=n;i++)
        scanf("%d%d",&l,&r),vec[r].push_back(l),cnt[l]++;
    for(int i=m;~i;i--)add(cnt[i],cnt[i+1]);
    f[0]=1,add(g[0],pw2[n]);
    for(int j=1;j<=m;j++)
    {
        for(int i=0;i<=m;i++)old_f[i]=f[i],f[i]=0;
        T.build(1,0,m);
        for(int i=j;i<=m;i++)
        {
            f[i]=T.query(1,0,m,0,i-1),add(g[j],1ll*f[i]*pw2[cnt[i+1]]%MOD);
            for(int k:vec[i])T.update(1,0,m,0,k-1,2);
        }
    }
    for(int i=0;i<=m;i++)
        for(int k=i;k<=m;k++)(k^i)&1?dec(h[i],1ll*g[k]*binom(k,i)%MOD):add(h[i],1ll*g[k]*binom(k,i)%MOD);
    for(int i=1;i<=m;i++)printf("%d\n",h[m-i]);
    return 0;
}