[problem] \color{blue}{\texttt{[problem]}} [problem]
[Solution] \color{blue}{\texttt{[Solution]}} [Solution]
这题最恶心的地方是卡空间。
我们先考虑不卡空间时怎么做。
直接并不好做，我们考虑正难则反，即利用容斥原理。答案应为从 a a a 没有任何限制经过 m m m 条边到 b b b 的方案数减去从 a a a 经过 m m m 条边到 b b b 且必须经过 c c c 的方案数。
自然地，我们会想到用 f m , i , j f_{m,i,j} fm,i,j 表示从 i i i 经过 m m m 到 j j j 的方案数。显然其初始条件 f 0 , i , i = 1 f_{0,i,i}=1 f0,i,i=1。
不难得到， f f f 的转移方程为：
f m , i , j = ∑ k → j f m − 1 , i , k f_{m,i,j}=\sum\limits_{k \to j}f_{m-1,i,k} fm,i,j=k→j∑fm−1,i,k
其中 k → j k \to j k→j 表示节点 k k k 可以到达节点 j j j。
很显然，由于每个节点可以到达的节点是一段连续的区间，我们可以用差分来优化我们的 dp \text{dp} dp。
表面上看，最终答案似乎就是
f m , a , b − ∑ k = 0 m ( f k , a , c × f m − k , c , b ) f_{m,a,b}-\sum\limits_{k=0}^{m} \left (f_{k,a,c} \times f_{m-k,c,b} \right ) fm,a,b−k=0∑m(fk,a,c×fm−k,c,b)
但是，这样的计数是错误的。因为我们可以多次经过 c c c 这个节点，而每一次经过节点 c c c 都会被重复计数。比如在一条途径中，我们在 3 , 7 , 9 3,7,9 3,7,9 次经过节点 c c c，那么我们在 k = 3 , 7 , 9 k=3,7,9 k=3,7,9 时都会把这条途径计入。
怎样避免重复？我们可以强制从 c c c 到 b b b 的路径不能再经过 c c c。那这样会不会导致计数遗漏？不会，因为从 a a a 到 c c c 的路径还是可以重复经过 c c c 的。
于是，我们可以新开一个数组 g m , i , j g_{m,i,j} gm,i,j 表示从 i i i 经过 m m m 条边到 j j j 但不能经过 i i i 的方案数。 g g g 的转移和 f f f 相似，只是 g l , i , i = 0 ( l = 1 , 2 , … , m ) g_{l,i,i}=0(l=1,2,\dots,m) gl,i,i=0(l=1,2,…,m)。
但是这题卡空间。
我们发现， f f f 和 g g g 在 m m m 时的转移都只和 ( m − 1 ) (m-1) (m−1) 有关。于是 f f f 和 g g g 完全可以重复利用，只需要开二维即可。这样是可以满足空间要求的。但是有个问题，就是我们不能随时询问随时回答，因为我们并没有保留任意的 m m m 的状态信息。
怎么办？不能在线回答询问，那就离线！于是主体思路完成。
就离线这一点，这题的难度上了一个台阶。
Code \color{blue}{\text{Code}} Code
const int mod=998244353;
inline void add(int &a,int b){a=(a+b>mod?a+b-mod:a+b);
}const int N=510,M=105;
int l[N],r[N],n,q,m;
int f[2][N][N],g[2][N][N];struct Query{int a,b,c,m,ans,f[M],g[M];
}Q[100010];int main(){scanf("%d%d",&n,&q);for(int i=1;i<=n;i++)scanf("%d%d",&l[i],&r[i]);for(int i=1;i<=q;i++){scanf("%d%d",&Q[i].a,&Q[i].b);scanf("%d%d",&Q[i].c,&Q[i].m);m=max(m,Q[i].m);}for(int i=1;i<=n;i++)f[0][i][i]=g[0][i][i]=1;//initfor(int k=0;k<=m;k++){bool s=(k&1),t=(s^1);//s 表示这一维的信息，t 表示下一维for(int i=1;i<=q;i++){int a=Q[i].a,b=Q[i].b,c=Q[i].c;Q[i].f[k]=f[s][a][c];Q[i].g[k]=g[s][c][b];if (k==Q[i].m) Q[i].ans=f[s][a][b];}memset(f[t],0,sizeof(f[t]));memset(g[t],0,sizeof(g[t]));for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if (r[j]){//可转移 add(f[t][i][l[j]],f[s][i][j]);add(f[t][i][r[j]+1],mod-f[s][i][j]);add(g[t][i][l[j]],g[s][i][j]);add(g[t][i][r[j]+1],mod-g[s][i][j]);}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){add(f[t][i][j],f[t][i][j-1]);add(g[t][i][j],g[t][i][j-1]);}g[t][i][i]=0;}}for(int i=1;i<=q;i++)for(int j=0;j<=Q[i].m;j++)Q[i].ans=(Q[i].ans-1ll*Q[i].f[j]*Q[i].g[Q[i].m-j]%mod)%mod;for(int i=1;i<=q;i++){Q[i].ans=(Q[i].ans+mod)%mod;printf("%d\n",Q[i].ans);}return 0;
}
