萌萌哒pyx来放题解啦。

第三题由于我是考后才想出来的，所以并没有实际测试，并且可能的解法很多，只是挑了一个更NOIp级别的做法来讲。

T1

考你会不会编程

T2

关键就是怎么样找到可能出现在路径上的点。

那么存在直接或间接地路径到终点，即为将所有边反向后，存在从终点到它的路径。

故只需要反向跑一边遍历，就知道哪些点是存在路径到终点的。

这样，再把所有边扫一遍，就可以知道 $i$ 号点是否可以出现在答案路径上。

由于边权均为1，剩下的只要把可以出现在答案路径上的点BFS一遍就可以了。

T3

解法很多，挑了一个解法。考场上我没有想出来……出了考场才会的。

首先，由于 $a_i$ 很大，联想到CTSC的因式分解那题（其实完全不用这么联想……），我们可以考虑在模意义下来检测。

这么做的正确性，在于几乎不会有不合法的点出现在解当中。不妨取一个 $10^9$ 级别的素数 $P$，那么由于将$10^6$个数带进去，而且可以近似地将答案看做随机数，那么出现一个$0$的概率为$\frac{m}{P}$，就几乎是千分之一了，故我们有$99\%$的可能性在总共10个测试点中不会出现这种情况。

这样，我们以此将$[1,m]$在多项式内求值，利用秦九韶算法可以在$n\times m$次long long乘法,$n \times m$次long long加法，$n \times m$次long long取模中将求值结果算出来。这样就可以获得70分。

但是我亲测这样，极限数据需要1.6s左右。许多大神们就开始用很多高大上的方法将这$m$个数中一些不可能的数去掉，而我试图求导来解方程结果失败了，这里不赘述。

那么，由于我们需要求的是$[1,m]$里所有正整数的答案，假设我们将答案求了出来，考虑将答案差分。

由差分的定理，$n$次多项式的值，差分$n+1$次之后，所剩的值全为0.这个定理比较好证明，这里不叙述。

我们的做法就是，先求出$1 \sim n+1$的$n$次差分的结果，我们可以知道，第$n+1$次差分的结果均为0，为了还原出$m$个数，我们在第$n+1$次差分之后的结果中，填充$m-n$个$0$，然后再还原回来即可。

假设$m>>n$，这样做的话，只需要$n \times m$次在模意义下的int加法即可完成。模意义下的int加法也可以在1次int加法、1次int大小比较与至多1次int减法内完成。这样就可以在1s内通过。