题意简述

你希望组合出一条长度为\(n\)的项链，给定\(a[1] \cdots a[n]\)，\(a[i]\)表示长度为\(i\)的项链的种类有\(a[i]\)种，问一共能组合出多少种长度为\(n\)的项链。答案对\(313\)取模。

多组数据，数据不超过20组。

数据范围

\[1 \leq n \leq 10 ^ 5\] \[1 \leq a[i] \leq 10 ^ 7\]

分治FFT

分治FFT用于快速计算以下类型的式子： \[f[n] = \sum _ {i = 0} ^ {n - 1} f[i]g[n - i]\] 这个式子与正常的\(FFT\)卷积式不同，可以发现\(f\)的每一项计算都需要前面所有项的信息，所以无法在一次\(FFT\)内将\(f[1]到f[n]\)的值计算完成。如果使用FFT暴力计算的话，时间复杂度为\(O(n ^ 2logn)\)，这通常是不能被接受的复杂度。

题意简述

给定\(g[0] \cdots g[n - 1]\)，求\(f[0] \cdots f[n - 1]\)，其中 \[f[i] = \sum _ {j = 1} ^ i f[i - j]g[j]\] 边界为\(f[0] = 1\)。答案模\(998244353\)。

数据范围

\[2 \leq n \leq 10 ^ 5\] \[0 \leq g[i] < 998244353\]

时间限制：1s 空间限制：128MB

题意描述

给定\(n\)个变量和\(m\)个式子，形如： \[a \geq b + c\] \[a \leq b + c\] \[a = b\] 这些变量必须为非负整数，如果能找到一组可行解，输出"Yes"，否则输出"No"。

时间限制（总）：10s 空间限制：128MB

题意简述

多组数据，给定一个有\(n\)个点\(m\)条边的有向带权图，如果图中存在负环输出"YES"，否则输出"NO"。

时间限制（总）：5s 空间限制：128MB

题意简述

给定一张\(n\)个点，\(m\)条带权边的有向无环图，边权值都是\(1\)，你可以调整其中的一些边的边权为\(2\)，来满足任意一条从点\(1\)到达点\(n\)的路径上的边权和相等。如果无解输出"No"，否则输出"Yes"，然后输出调整后所有边的边权。

时间限制：2s 空间限制：256MB

题意简述

给定\(N\)个变量和\(K\)个式子，形如： \[A = B\] \[A < B\] \[A \geq B\] \[A > B\] \[A \leq B\] 这些变量必须为正整数，求出一组符合所有条件的最小解，如果无解，输出\(-1\)。

时间限制（总）：10s 空间限制：128MB

差分约束系统

差分约束系统，是一类关于不等式组的线性规划问题。给定\(n\)个变量和\(m\)个形如\(x_i - x_j \leq val(val已知)\)的不等式，要求出一组可行解或求出一组最小/大化 \(x _ t - x _ s(s,t给定)\)的解。

题意简述

给定一个\(n(2 \leq n \leq 10 ^ 4)\)个点，\(m(1 \leq \ 5 * 10 ^ 4)\)条边的有权无向图，\((0 \leq 边权 \leq n)\)，你可以将其中的\(k(0 \leq k \leq 10)\)条边的边权设为\(0\)，给定起点和终点，求起点到终点的最短路径。

时间限制（总）：10s 空间限制：128MB

题意简述

有一个\(n * n(n \leq 2 * 10 ^ 4)\)的矩阵，矩阵上只能横着或竖着移动，移动代价是\(2/每格\)。矩阵上还有\(m(m \leq 10 ^ 5)\)个点可以原地不动改变移动的方向（横着变为竖着，竖着变为横着），代价为\(1/每次\)。给定起点和终点，求从起点移动到终点的最小代价。如果从起点出发无法到达终点，输出\(-1\)。

时间限制（总）：10s 空间限制：128MB