提交答案.
考虑仔细观察数据特点.
测试点 1
特点: 图是由每个奇数点 $i$ 向 $i+1$ 连 $1$ 的边,向 $i+2$ 连 $0$ 的边,每个偶数点 $i$ 向 $i+1$ 连 $0$ 的边构成的.
询问 $(u,v,w)$ 时,特判 $u=v$ 的情况.否则,若 $u$ 为偶数,将它变成 $u+1$ ,若 $v$ 为偶数,将它变成 $v-1$ .
此时 $u,v$ 都是奇数,每次考虑让 $u$ 的编号 $+2$ .
若走 $u\to u+1\to u+2$ ,长度为 $1$ ,走 $u\to u+2$ ,长度为 $0$ .
那么可以得到答案为 ${(v-u)/2\choose w}$ .
模数不是质数,把它分解成 $2^{12}\times 3^8$ 后分开做,大概和拓展 Lucas 的做法差不多,最后 crt 合并.
测试点 2
特点: 图是一条 $1\sim n$ 的链,链上边权为 $0$ ,每个点再向自己连出自环,自环有边权.每次询问的 $u$ 都为 $1$ .
设 $f(i,j)$ 表示从 $1$ 走到 $i$ ,路径边权和为 $j$ 的方案数.
注意一个自环可以走多次,所以是一个完全背包.
测试点 3
特点: 图和测试点 2 一样,但询问的 $u$ 不一定为 $1$ .
跑 $n$ 次完全背包.
本机大概跑了 80s .
测试点 4
特点: 点数 $n$ 只有 $5$ .
设 $f(i,j,k)$ 表示从 $i$ 走到 $j$ ,经过的边权和为 $k$ 的方案数.
$k$ 这一维是有拓扑序的,先枚举 $k$ 就可以完成转移了.
本机大概跑了 120s.
测试点 5
特点: 把 $2$ 条边看成一组,每组都是 $i\to k,k\to j$ 的形式,且 $i,j\le 10$ ,各组的 $k$ 互不相同.
把每一组的两条边并在一起,就变成测试点 4 了,只是点数变成了 $10$ .
本机大概跑了 10s.
测试点 6,8,10
特点: 所有的边权都是 $1$ .
先处理出邻接矩阵 $A$ ,其中 $A_{i,j}$ 表示从 $i$ 到 $j$ ,经过 $1$ 条边的方案数.
那么根据矩阵乘法的定义,容易发现 $A^w_{i,j}$ 就表示从 $i$ 到 $j$ ,经过 $w$ 条边的方案数,即边权和为 $w$ 的方案数.
倍增预处理出 $A^1,A^2,A^4\dots$ ,询问时,只用 $A^w$ 和 $u$ 那一列的向量乘起来的贡献就可以了.
时间复杂度 $O(n^3\log w+q\cdot n^2\log w)$ .
其实有多项式的更优做法,不过反正是提答题,就咕了.
测试点 7
特点: 绝大部分边权都是 $1$ ,只有很少的边权为 $2$ .
对于每条边权为 $2$ 的边,新建一个点,把这条边拆成两条边权为 $1$ 的边,然后就和测试点 6,8,10 一样了.