552这个题其实是我搞研究的时候遇到的小问题，比较简单&比较有趣就拿来主义给大家练个手了。背后的理论体系其实蛮大的，而且OI里面没引入，抛砖引玉介绍一下，你们懂的。

Weighted Automata：

形式上而言，对于一个半环$S$与一个字符集$\Sigma$，我们可以定义一个带权自动机$\mathcal{A}$，由以下部分组成：

1. 状态集合$Q$.
2. 带权初始状态与结束状态$I, T:Q\rightarrow S$.
3. 转移矩阵$E:\Sigma\times Q\times Q\rightarrow S$.

那么对于输入串 $w=a_1a_2...a_l$, $\mathcal{A}$输出$IE_wT=I\left(\prod_{i=1}^l E(a_i)\right) T$.

直观而言，带权自动机是非确定性自动机的一个小扩展，每条边有边权（对于输入边与输出边也成立），对于给定串的输出是每一条可能接收串的路径的边权乘积的总和。如果$S=\mathbb{N}$，则可以理解为是可被接收的路径数量。取$S=\mathrm{Bool}$，则该定义退化成非确定性自动机。

Weighted Language/Formal Power Series:

类比于自动机与语言的关系，带权自动机实际上接受带权语言，现代的术语也称它为形式幂级数。形式化定义就是一个函数 $\Sigma^*\rightarrow S$。

同样，类比于正则语言，也可以找到一类形式幂级数精确刻画可以被带权自动机接受，被称为有理形式幂级数。

关于有理形式幂级数有一大堆理论，具体可以参考Jean Berstel写的《Non-commutative Rational Series with Applications》，不过这本书比较晦涩，但是囊括了很多结果。

等价性判定

Samuel Eilenberg在1974年的书《Automata, Languages and Machines》里证明了，对于$S=\mathbb{N}$的情况，两个自动机等价仅当：对于长度不超过两个自动机状态总量的串，他们输出相等。

这变相提供了一个PSPACE的等价性判定算法（当字符集是有限的），只需要枚举有多项式上界长度的串即可。

同时，我们可以构造多项式$P_n[(x_{i, a})_{i\in[n], a\in\Sigma}]=\sum_{w\in\Sigma^*, |w|\leq n} IE_wT x_w$，其中 $x_w=x_{1, a_1}x_{2, a_2}\cdots x_{l,a_l}$.

注意到这个多项式分别列举了所有长度不超过$n$的串，自动机的等价性可以转化为两个多项式等价性的判定，其中所有系数都是自然数。这个问题是一个经典的问题，只需要给每一个变量均匀随机生成一个在$[d/\epsilon]$里的元素并带入多项式检测，其中$d$是多项式次数，那么检测失败概率不超过$\epsilon$。

在程序等价性判定中的应用

经典的程序的控制流图可以使用自动机来描绘，所以自动机等价性有着其独特的意义。

对于更加复杂的程序，比如带有概率的程序，或者量子计算机中的程序，它们的控制流图实际上是一个带权自动机，因为不同的道路都可能有概率/振幅经过。所以我们可以把两个程序的控制流图用带权自动机描述出来，然后套用带权自动机来验证一些情况下的程序等价性。

这种方法在编译器规则验证中有广泛应用环境，可以在控制流图层面对优化规则进行正确性证明。

理论上的更多问题

留一些可以思考的问题（虽然大都有人解决过了）给大家思考：

1. 如何引入ε-转移？如何消去ε-转移？
2. 如何判定一个带权自动机的输出是否一定小于等于另一个带权自动机的对应输出？
3. 如何最小化带权自动机（最小化状态数）？
4. 带权自动机的输出大小是否可以被界住？
5. 哪些形式幂级数是有理的？什么样的构造可以得到有理形式幂级数？
6. 单字符的带权自动机是否有更好的性质？

这里面有很多问题都是不可判定的，所以总的而言这个事情还挺难的。

总结

自动机理论里还有很多很有趣的问题、技术并不广为人知，它们在实际生产中有举足轻重的地位，大家感兴趣可以稍微学习一些。

以上。

萌萌哒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内通过。