题解【No cost too great】

· · 题解

传送门

前置知识：

差分，容斥。

题意：

分析：

是一道容斥+dp+小幅度卡空间题。

Subtask0：

dfs 暴力搜索。

Subtask2:

先来看看没有容斥、不卡空间的 dp 该怎么做。

考虑一个 dp 数组 f_{k,s,t}，表示从 s 经过 k 条边到达 t 的方案数。转移方程是 f_{k,s,t}\gets\sum_{(v,t)\in E} f_{k-1,s,v}，时间复杂度为 O(n^3m)。将这个方程反过来，就是 f_{k-1,s,v}\to f_{k,s,t}\quad((v,t)\in E)。关注到每个点所到达的点都在一个区间中，也就是说这个式子是一个区间加法。区间加法可以通过前缀和或者差分实现。这里我选择差分，那么转移就变成了如下：

for(int k=1; k<=M; ++k) {
    for(int s=1; s<=n; ++s) {
        for(int t=1; t<=n; ++t) {
            f[k][s][L[t]]+=f[k-1][s][t];
            f[k][s][R[t]+1]-=f[k-1][s][t];
        }
        for(int t=1; t<=n; ++t) {
            f[k][s][t]+=f[k][s][t-1];
        }
    }
}

询问可以在线回答：

while(q--) {
    int a=read(), b=read(), c=read(), m=read();//这里的c暂时没用
    printf("%d\n", f[m][a][b]);
}
Subtask3:

加入容斥，显然不经过点 c 的方案等价于所有方案减去经过点 c 的方案。一种很符合直觉的计算经过点 c 方案数的方法是 \sum_{i=0}^kf_{i,s,c}\cdot f_{k-i,c,t}，但是很显然，这样会有重复的方案。当两个方案中最后一次经过 c 点的时间不同时，这两个方案一定不同，并且我们知道单个 f 数组中并没有重复的方案，那么就可以通过枚举最后一次经过 c 点的时间来进行计算。现在再增加一个 dp 数组 g_{k,s,t}，表示从 s 出发，经过 k 条边且不再经过 s 到达 t 的方案数，这样就可以通过 \sum_{i=0}^kf_{i,s,c}\cdot g_{k-i,c,t} 来计算不重复的经过点 c 的方案数了。在转移数组 g 时，只需要令 g_{k,s,s} 的值始终为 0，就可以保证所有 g_{k,s,t} 方案都没有再次经过点 s。转移如下：

for(int k=1; k<=M; ++k) {
    for(int s=1; s<=n; ++s) {
        for(int t=1; t<=n; ++t) {
            f[k][s][L[t]]+=f[k-1][s][t], f[k][s][R[t]+1]-=f[k-1][s][t];
            g[k][s][L[t]]+=g[k-1][s][t], g[k][s][R[t]+1]-=g[k-1][s][t];
        }
        for(int t=1; t<=n; ++t) {
            f[k][s][t]+=f[k][s][t-1];
            g[k][s][t]+=g[k][s][t-1];
        }
        g[k][s][s]=0;
    }
}

询问仍然是在线回答：

while(q--) {
    int a=read(), b=read(), c=read(), m=read(), ans=f[m][a][b];
    for(int i=0; i<=m; ++i) ans-=f[i][a][c]*g[m-i][c][b];
    printf("%d\n", ans);
}
Subtask4:

不出意外的话，此时的数组大小在 200MB 上下，完全无法通过 128MB 的限制。但是询问是可以离线的，意味着我们并不需要将 f 和 g 两个数组都完全存下来。这里选择滚动 g 数组，所以先把 f 数组计算出来，然后在滚动计算数组 g 的同时计算答案。主题代码如下（未进行取模）：

#define rep(i, a, b) ...
inline int read(){...};
const int N=502, M=100, Q=1e5+1;

int n, q, L[N], R[N], f[M+2][N][N], g[2][N][N];
struct Que {
    int a, b, c, m, ans;
    inline void sol(int k) {
        if(k<=m) ans-=f[m-k][a][c]*g[k&1][c][b];
    }
} que[Q];
inline Que get() {
    int a=read(), b=read(), c=read(), m=read();
    return Que(a, b, c, m, f[m][a][b]);
}

int main() {
    //输入 
    n=read(), q=read();
    rep(i, 1, n) {
        L[i]=read(), R[i]=read();
        f[0][i][i]=g[0][i][i]=1;
        if(!L[i]) L[i]=1;
    }
    //计算数组 f 
    rep(k, 1, M) {
        rep(s, 1, n) {
            rep(t, 1, n) {
                f[k][s][L[t]]+=f[k-1][s][t]);
                f[k][s][R[t]+1]-=f[k-1][s][t];
            }
            rep(t, 1, n) {
                f[k][s][t]+=f[k][s][t-1];
            }
        }
    }
    //输入与预处理询问 
    rep(i, 1, q) {
        que[i]=get();
        que[i].sol(0);
    }
    //计算数组 g 与答案 
    rep(k, 1, M) {
        bool kk=k&1, tk=kk^1;
        memset(g[kk], 0, sizeof(g[kk]));
        rep(s, 1, n) {
            rep(t, 1, n) {
                g[kk][s][L[t]]+=g[tk][s][t];
                g[kk][s][R[t]+1]-=g[tk][s][t];
            }
            rep(t, 1, n) {
                g[kk][s][t]+=g[kk][s][t-1];
            }
            g[kk][s][s]=0;
        }
        rep(i, 1, q) que[i].sol(k);
    }
    //输出答案 
    rep(i, 1, q) printf("%d\n", que[i].ans);
}

时间复杂度为 O(n^2m+mq)，空间大概在 100MB 上下。

其他的话

本题可以进一步对空间进行常数级别的优化，最后将空间控制在 54MB 上下，是通过只存储奇数步的 f 数组来完成的，在计算答案的时候对 f 进行一次转移。但是这种方案是用时间换空间，本质上并无区别，（并且肯定会被骂）所以就没有作为本题正解。