【空洞骑士】容斥区间差分dp

Magic_World · 2022-08-28 20:22:13 · 个人记录

【空洞骑士】容斥区间差分dp

光芒浸透圣巢，她正犯下弥天之错。

所剩寥寥无几的信仰，为什么始终执着。

我将作灯塔，照耀王国。

但在那之前有更重要的事去做，

无论什么代价都在所不惜，尽管我所剩无多……

白王正在最后一次参观他建造的宏伟宫殿。现在假设宫殿由 n 个房间构成，房间之间有若干个单向通道。出于白王奇怪的装修癖好（不是指到处安电锯），对于第 i 个房间，它向编号在区间 [l_i,r_i] 中的所有房间都连有一条单向通道。例如，4 号房间向 [2,5] 连有单向通道，就意味着从 4 号房间到 2,3,4,5 号房间各有一条单向通道（一个房间可以向自己连有通道）。当一个房间向 [0,0] 连有通道时，表示没有从这个房间出发的通道。

白王提出了 q 个问题，每次询问从 a 号房间，通过恰好 m 条单向通道且不经过 c 号房间到达 b 号房间的方案数（两方案不同，当且仅当存在 i 使得两方案通过的第 i 条通道不同）。因为这个数字可能会很大，所以白王让你将答案模 998244353 后再回答。

输入格式

第一行，两个整数 n, q 表示点数和询问数。

接下来 n 行，每行两个整数 l, r，第 i+1 行的整数 l_i, r_i 表示 i 号节点向区间 [l_i, r_i] 中的每个点都连了一条单向边。当 l_i=r_i=0 时，表示该节点没有向任何点连边。

接下来 q 行，每行四个整数 a, b, c, m 表示一个询问。

输出格式

反向思考，对于每一个 f[k-1][s][v] ,它都对 (v,t)\in E 的 f[k][s][t] 有贡献。

而本题中 v 连向的点是一个区间 [L_v,R_v]，所以可以用差分维护 f 数组的第三维。

for(int k=1;k<=Maxm;++k)
{
    for(int s=1;s<=n;++s)
    {
        for(int v=1;v<=n;++v)
        {
            f[k][s][L[v]]+=f[k-1][s][v];
            f[k][s][R[v]+1]-=f[k-1][s][v];//差分
        }
        for(int t=0;t<=n;++t)
        {
            f[k][s][t]+=f[k][s][t-1];//差分求和
        }
    }
}

再考虑不经过 c 点这个条件：

感性上考虑，经过 c 点的方案数是 \sum\limits_{i=0}^k f[i][s][c]*f[k-i][c][t]；

但是这之中有重复方案，例如 ： abcabcabc

每个c都可以作为中转点，但三个 c 的方案是一模一样的。

那么如何排除重复情况呢？

注意到，强制要求中转点的 c 是这条路上最后一次经过 c ，即可排除重复。

设 g[k][s][t] 表示 s 经过 k 条边到达 t 且路上不再经过 s 的方案数。

注意，初始化时 f[0][s][s]=g[0][s][s]=1

转移同理 f ，但每次转移到 k(k>1) 时，都要保证 g[k-1][s][s]==0 ，这样就不会出现经过多次 s 的情况。

代码

for(int s=1;s<=n;++s)
{
    f[0][s][s]=1,g[0][s][s]=1;//初始化
}

for(int k=1;k<=M;++k)
{
    for(int s=1;s<=n;++s)
    {
        for(int v=1;v<=n;++v)
        {
            f[k][s][L[v]]+=f[k-1][s][v];
            f[k][s][R[v]+1]-=f[k-1][s][v];
            g[k][s][L[v]]+=g[k-1][s][v];
            g[k][s][R[v]+1]-=g[k-1][s][v];
        }
        for(int t=0;t<=n;++t)//注意区间有[0,0]
        {
            f[k][s][t]+=f[k][s][t-1];
            g[k][s][t]+=g[k][s][t-1];
        }
        g[k][s][s]=0;//保证不经过第二次 s
    }
}