ARC099F Eating Symbols Hard
有一段标号从 −∞ 到 +∞ 的序列 A，初始是 Ai=0。现在有一个人在 0 位置，有一段操作序列 s，依次进行操作。
假设 i 时刻这个人在位置 p，如果 si 是 '+'，则将 Ap 加 1，如果是 '-'，则减 1；如果是 '<' 则该人左移一格，否则是 '>' 则右移一格。
要求数出 s 的所有连续子串中最终得到的 A 与 s 最终得到相同 A 序列的个数。
数据范围 ∣s∣≤250000。
考虑构造一波类似生成函数的东西 f(x)=∑i=−∞+∞Aixi，另外还有一个指针 g，开始是 g 指向 0 位置，显然初始时 f(x)=0。
我们令 fi(x) 表示 1∼i 这一段子串操作所得到的 f 值，gi 表示 1∼i 操作后的指针位置。考虑在末尾加入一个字符 c，如果 c 是 '+' 或 '-'，那显然 {fi(x)=fi−1(x)±xgigi=gi−1，同理如果 c 是 '<' 或 '>'，那显然 {fi(x)=fi−1(x)gi=gi−1∓1。
如果要计算 [l,r] 的 f 值，不难发现就是 xgl−1fr(x)−fl−1(x)。
于是我们要算的就是 fn(x)=xgl−1fr(x)−fl−1(x)，考虑随便选一个 x，算出这个多项式的值然后哈希一下即可。
代码
AGC041D Problem Scores
问存在多少个长度为 n (2≤n≤5000)n\,(2\le n\le 5000)n(2≤n≤5000) 的单调不减序列 aaa，满足 1≤ai≤n1\le a_i\le n1≤ai≤n，且...
AGC029F Construction of a tree
题意大概就是给你 n−1n-1n−1 个点集，全集是 {1,2,…,n}\{1,2,\dots, n\}{1,2,…,n}，现在要从每个点点集中抽出两个点来连边，最终形成一棵树。让你输出方案或...
