CTSC2016 NOIP十合一 题解
$\text{Description}$
给定一张边带权有向图与模数，多次询问一个点到另一个点间距离为某个值的路径的条数对给定模数取模的值。
注意一个细节，即任意点到其自身存在一条长度为 $0$ 的“道路”。
提交答案题。
$\text{Solution}$
C1
性质
形如下图：
模数为 $2^{12}\times 3^8$。
什么，你说懒得打质因数分解？百度质因数分解不谢。
做法
设当前询问为 $u,v,w$。
每一个奇数到下一个偶数的路径长为 $1$，每一个偶数到下一个奇数的路径长为 $0$。
若 $u$ 为偶数，我们强制其退回上一个奇数，然后执行 $w\gets w-1$。
若 $v$ 为偶数，我们强制其前往下一个奇数。
那么现在 $u,v$ 都为奇数，我们考虑从某个奇数跳往下一个奇数时，有两种方案可选，一种花去 $1$ 长度，另一种不花去长度。
设 $l$ 表示从 $u$ 跳到 $v$ 要跳多少次，注意此处 $w$ 是更新过的。
那么我们需要计算的是：
这个模数不是质数，得想个方法快速计算组合数。
然后你发现一波扩展卢卡斯定理（exLucas）解决了？
递归切题法，启动！
细节判一下就能过了，时间复杂度 1s 跑的完（
代码
1 |
|
点评
强行扩展卢卡斯，差评（
C2
性质
从点 $1$ 到点 $100$ 顺次相连形成一条链，且每个点上有一个自环。
询问中的 $u$ 都为 $1$，$w$ 不超过 $50000$。
做法
从一个数到其后继不需要花费边权。
我们可以任意挑选自环（可以重复挑选同一个自环），使得所选择自环上的边权和为 $w$，然后求方案数。
完全背包求方案数？
由于模数的问题，我们老老实实做 DP 就可以了，注意状态设计时不能压掉前面那一维。
都做这题了还不会完全背包？不会吧不会吧不会吧？好吧我不会……
代码
1 |
|
点评
好像没啥好说的……
C3
性质
从点 $1$ 到点 $10^4$ 顺次相连形成一条链，且每个点上有一个自环。
询问中 $w$ 不超过 $1000$。
模数 $1998585857=953\times2^{21}+1$，其原根为 $3$。
做法
跟 C2 差不多，但是数据范围上有从量到质的变化。
如果直接 DP，那么 C3 会跑死，这时候就要祭出多项式了。
设第 $i$ 个物品的生成函数为 $F_i(x)$，其重量为 $w_i$，那么它的生成函数是很容易写出来的（除了 $w_i$ 的倍数上有 $1$ 其它都为 $0$，注意这边认为 $0$ 也是 $w_i$ 的倍数）。
每次询问我们只需求出某一个区间内所有物品的生成函数的乘积。
注意到询问中 $w$ 不超过 $1000$，故多项式最多只有 $1001$ 项。
预处理前缀生成函数乘积与其逆即可。
注意 $1998585857$ 加起来会爆 int。
代码
1 |
|
点评
啥也不说了，$998244353$ 天下第一！！
C4
性质
$n=5$，边权较小的边重复出现次数较多，询问中 $w$ 不超过 $50000$。
做法
这个 $n$ 很小，开数据时想这个点应该是个暴力点？
然而边数过多，没想到较好的暴力，故考虑 DP。
设 $f(u,v,w)$ 表示从 $u$ 到 $v$ 边权和为 $w$ 的路径数，易有转移：
时间复杂度 $\Theta(n^2w+nwm)$（考虑每条边在转移时贡献的次数），暴毙。
再回顾本题性质：
- 可能会有部分状态是无用的。
- 有些边的出现次数较多。
我们考虑换一个 DP 方式，首先对每类起始点相同的边按边权从小到大排序，然后按顺序枚举状态（当然你需要初始化：每个点到它自身有一条边权和为 $0$ 的路径），若其非零，则用 $v$ 的出边更新别的状态，对于我们所更新的这个状态，若其 $w$ 超过 $50000$，则跳过，顺便可以跳过同一个终点的更新，因为我们已经进行了排序。
注意这个模数仍然是 C3 的 $1998585857$。
代码
1 |
|
点评
跑一次 1 min，酸爽。
C5
性质
图由若干个三元链组成。每个三元链的中心是 $11\sim50000$ 节点，两端是 $1\sim 10$ 节点。
边权不超过 $200$，询问中的 $w$ 不超过 $10000$。
做法
容易发现任意 $11\sim 50000$ 节点都只有一个前驱和一个后缀，故询问时可以强制其跳到它的前驱/后缀（$1\sim 10$ 节点跳到其本身即可）。
所以一个三元链可以等价为 $1\sim 10$ 节点间的连边，可以采用 C4 的做法。
哦，注意这个模数仍然是 C4 的 $1998585857$（不过直接搬 C4 代码应该没有这个问题）。
代码
1 |
|
点评
什么叫做 10s 跑完啊？（战术后仰）
C6
性质
$n=200$，边权全为 $1$。
做法
矩阵快速幂？但是询问中的 $w$ 互不相同，朴素地做时间复杂度为 $\Theta(qn^3\log w)$，这可不能像 C4，C5 那样暴力跑 1min/10s 能解决的。
注意到我们每次只需要求出矩阵的一个点，那么我们预处理邻接矩阵的 $2^0,2^1,\cdots,2^{30}$ 的幂，每次询问通过二进制分解不断将预处理出来的矩阵乘到从单位矩阵拎出来一列所形成的列向量上。
时间复杂度 $\Theta(n^3\log w+qn^2\log w)$。
代码
1 |
|
点评
算是矩阵快速幂比较进阶的应用姿势？跑了 300s。
C7
性质
$n=100$，有 $100$ 条边的边权为 $2$，其它边权全为 $1$。
做法
一开始看到第一条边的边权还以为我手贱改了啥……然后又下载了一次数据发现没有错……
所以本题的核心在于处理多出来的边权为 $2$ 的边。
然后对这个边权为 $2$ 的边建一个新点，变成两条边权为 $1$ 的边？
套用 C6 的做法即可。
代码
1 |
|
点评
基操。又颓了 6min 知乎，然后次日的语文卷子没写。
C8
性质
$n=1000$，边权全为 $1$，询问中的 $u$ 都为 $1$。
做法
这个数据范围很棘手，要不先套 C6 的做法试试？
开始跑……跑不动了，关掉，虽然只跑了一小会。
然后发现特征多项式那一套不是很会，又看到有人说跑一小时，心想：一小时就一小时吧。
结果 1023s 出结果？
点评
暴力出奇迹！
C9
性质
$n=10000$，边权全为 $1$，边 $(u,v)$ 满足 $u\equiv v+1\pmod{10^3}$，对于所有询问 $(a,b,c)$，满足 $b-a\equiv c\pmod{10^3}$。
做法
用 C6 的做法是不可能的，空间会卡爆。
考虑边和询问的特点，如果我们将点分为 $10^3$ 类，第 $i$ 类表示编号对 $10^3$ 取模后值为 $i$ 的点，那么边相当于一个类往其后继类连边，询问则是为了使得在边的限制下存在解而限制的，且我们可以得出在这些类中走了多少圈。
那么设出矩阵 $G_i$ 表示第 $i$ 类点到第 $i+1$ 类点的邻接矩阵，那么实际上是对应的行向量依次乘上 $G_{u\bmod{10^3}},G_{(u\bmod{10^3})+1},\cdots,G_{v\bmod{10^3}}$。
预处理 $G_0\times G_1\times\cdots\times G_{10^3-1}$，然后上式完整的所有类的乘积可以直接套用 C6 的做法解决，其它暴力即可。
点评
3min 跑完，挺快的。
C10
性质
$n=3000$，边权全为 $1$。
做法
不能 #define int long long 了，否则空间卡爆。
继续套用 C6 的做法，暴力出奇迹。
然后开着跑了很久很久……
点评
从八点半跑到了十点半，虽然等得很辛苦，但是一想到这段时间划了很久水，顺便写了 R2A 这算给 QkOI#R2 打广告吗 的相关内容，甚至不用去写特征多项式等神仙玩意儿，我便感觉，暴力出奇迹的生活，是多么的朴实无华，且枯燥。