之前构造的题单的原md文件由于我作死乱扩容分区，导致电脑基本全部文件损坏，丢失......

估计除非我能稳定做2000分的构造，短时间是不会更新了

（想要变强，就继续写构造了，但是不代表我已经可以稳定做2000分的构造了...）

这个题解估计不会更新的太快，做构造已经占了我很大时间了，这个题解应该会随缘更新吧，如果遇到好的题就会加进来

Update:

2023.3.21: 第一题，其实是很久之前写了一半题解，今天更新构造的题解，顺便把这个也更新一下

2023.3.22:第二题，是很早之前做的题，不得不再提醒一下，这个坑（指这个题解）我真的不一定能稳定地填上（

心得

0、在用 dp 解出一道题前，要能够先想到它是能够用 dp 解出来的，看起来像废话，但实际上的意思是，观察出它内在的重复子结构，明白答案可以由之前的状态计算过来

1、如果想要用 dp 解出一道题，必须要先把状态定义好，如果没有定义好状态，那么状态推导就无从谈起了

2、相对来说简单的题，可以直接按照题目所求来定义状态，如第一题，我们就可以在写小样例时就发现了状态的重复利用，从而发现了，可以用 f_i 来表示，对于长度为 i 的区间，能够组成的方案数

3、可以通过状态转移方程来发现当前状态计算所依赖的状态，从来进行优化（第二题），如滚动数组

题意

给定 2n 个点，要求将点划分成 n 对，这样的一对点，就会构成一个区间。问有多少种划分，能使得划分满足以下条件：

对于任意两个区间，要么一方包含另一方，要么长度相等

数量对 998244353 取模

思路

首先从条件入手，这是唯一的线索

我们可以尝试从小样例构造情况

但需要注意的是，有些划分看起来合法，但是是不合法的

感觉上很对，但其实对于点对 (2, 3) 和 (5, 8) 组成的区间，它们既不是长度相等，要不是一方包含另一方

我们考虑枚举第一个区间的长度

需要注意的是，第一个区间的左端点一定是在 1 号点上

而且，所有的区间，都不能比这个区间更长，这个是好理解的

现在我们重新定义一下区间的长度为区间除了左端点和右端点，中间有几个点

我们可以发现，我们可以用同样长度的区间，在原区间的位置向右移，像这样

这样的区间一定是合法的

但是它却不一定可以匹配任意的 n

这样就一定无法匹配

所以我们考虑怎么先放好相同长度的区间

设区间的长度是 k ，可以发现，如果我们的 k\geq n-1 ，那么直接横着就可以铺满，那么中间就会剩下一些空位，如

那么这些的空位就可以直接调用 f_j

那如果我们的 k

像这样也是合法的，而且它的贡献就是 1 ，而我们可以发现，这实际上就是求 n\%(k+1)=0 的数量

也就是求约数个数，当然，要减去 1 ，因为可以发现，当 k=n-1 时，也就是 k+1=n ，同样是一个约数，但是已经在 f_j 中记过贡献了

现在还剩下一个问题

我们可以发现，如果直接去做的话，应该是 O(n^2) 的复杂度，因为我们在枚举 k 时，会调用到各个 f_j

但是如果将一个 f_i 展开来看，比如 f_8 ，应该是 f_8 = f_0+f_2+f_4+f_6+约数个数-1

也就是说，后面的就是 f 的前缀和

这里我们选择用 O(nlogn) 来预处理出各个数的约数个数

代码

闲话

这题是上上上周和队友vp时做的，本来 dp 是队内的 dp 大手子，子锋，解决的，没想到我竟然自己做出来了，给了我很大的自信心233（但不得不说，他在 dp 甚至是算法和数据结构上都比我强很多，知道很多知识点）

题意

你站在 n\times m 二维 01 矩阵 mp 的 (1,1) ，每次可以选择向下走或者向右走，要到达 (n,m) ，现在规定合法的路径为，从起点到终点，起码走了 p 个 0 ， q 个 1 ，问这样合法的路径数在模以 998244353 后的结果

思路

不考虑各种时间限制、题目限制，可以发现这就是一道很经典的 dp 问题，所以我们会很自然地想到 dp 的解法

先不考虑数据量的大小，定义一个初步的状态

f_{i,j,k,l} 表示，从起点到达 (i,j) ，在走了 k 个 0 ， l 个 1 的条件下，有多少种方案

那么 \sum_{k\geq p,l\geq q}f_{n,m,k,l} 就是答案

这样的状态推导很简单，简单分类一下就好

当 mp_{i,j}=0

$$ f_{i,j,k,l}=f_{i-1,j,k-1,l}+f_{i,j-1,k-1,l} $$

当 mp_{i,j}=1

$$ f_{i,j,k,l}=f_{i-1,j,k,l-1}+f_{i,j-1,k,l-1} $$

解是解出来了，但是我们一算数据量就会发现，时间和空间复杂度是 O(nmpq) 的，因为四个维度都要暴力枚举

计算量达到了 2.5e5*1e8 ，这明显是不能接受的，所以我们应该在这个基础上进行优化

我们需要注意到以下的细节：

1、虽然 p,q 可以达到 1e4 ，但是我们根本不可能真的达到

为什么呢？

考虑从 (1,1) 到达 (n,m) ，我们应该会经过 n+m+1 个点

那么我们就可以把计算量降到 2.5e5*1e3*1e3

2、我们不需要真的枚举四维，只需要枚举三维，即 i,j,k 即可

为什么呢？

可以发现，从起点到一个给定的点 (i,j) ，我们经过的点的数量也就被定下来了，是 i+j-1 ，所以，如果我们知道走过的 0 的数量为 k ，就可以知道走过的 1 的数量是 i+j-1-k

既然这样，我们又把计算量降到 2.5e5*1e3 ，这个复杂度已经很接近于能过题了

可以发现，在时间上，我们并不会跑满 2.5e5*1e3 ，因为有一些状态是不合法的，比如 k>i+j-1 ，这就意味着，我们光 0 的个数就超过了路径上点的个数，可以证明，计算量会降到能AC的限度

但是空间复杂度却不行，因为，无论如何，都要开出 2.5e5*1e3 的空间

观察状态推导方程，可以发现，我们的状态只依赖于当前一行和上一行，于是我们就用滚动数组优化即可，可以优化到 5e2*1e3

代码