有 $T$ 组数据，每组数据有一个长度为 $n$ 的 $\tt 01$ 字符串，求构造一个 $n$ 个结点的树满足每个结点的度数的奇偶性符合 $\tt 01$ 串 $s$，且将这些点依次排列到一个环上，任意两条边不在非端点处相交。

$1\le n\le 2\times 10^5$。

给定 $N$、$S$ 和长度为 $N$ 的序列 $A$，找到满足以下条件的序列 $X$ 的个数对 $998244353$ 取模后的结果：

• $X$ 的每个元素都是正奇数
• $\sum X_i=S$
• 设 $Y_i=\sum\limits_{j=1}^iX_j$，那么对于所有 $1\le i\le |X|,1\le j\le N$ 的 $i,j$，都满足 $Y_i\not=A_j$

$1\le N\le 10^5$

$1\le A_1<A_2<\dots<A_N<S\le10^{18}$

给定仅存在小写英文字母的字符串 $S, T$。你需要将 $T$ 分割成 $k$ 个 $S$ 的前缀（或着说用 $ S $ 的若干个前缀组成 $T$），最小化 $k$，输出最小值。若 $k$ 不存在输出 -1。

$1 \leq |S|,|T| \leq 5\times 10^5$

有三种不同颜色的球，分别有 $A,B,C$ 个。（相同颜色的球之间不区分）

将球放入 $N$ 个不同的盒子中，要求：

• 每个盒子至少放了一个球

• 每个盒子不能存在两个相同颜色的球

• 可以不放完所有的球

求放置方案数对 $998244353$ 取模的结果。

$1 \leq N \leq 5 \times 10^6$，$0 \leq A,B,C \leq N$

有一个 $n$ 个节点的有向图 $G$，对于所有的 $1 \le i, j \le n$ 且 $i \not= j$，都有一条权值为 $(a_i + b_j) \bmod m$ 的边连接 $i$ 和 $j$，请你求出 $G$ 从 $1$ 到 $n$ 的最短路。

P1758 [NOI2009] 管道取珠

考虑一个字符集合$A$（$A$中元素互不相同）和一个长度为$n$的字符串$S$，其中$S$中的字符都属于集合$A$。

给你一个包含 $m$ 个整数的序列 $b$ ($b_1<b_2<\dots<b_m$)。你可以对字符串 $S$ 作以下的操作：

1.选择一个合法的 $i$ ,并且令 $k=b_i$ ;

2.取出 $S$ 中前 $k$ 个字符 $Pr_k$ ;

3.取出 $S$ 中后 $k$ 个字符$Su_k$ ;

4.将 $S$ 中前 $k$ 个字符替换成翻转后的 $Su_k$ ;

5.将 $S$ 中后 $k$ 个字符替换成翻转后的 $Pr_k$ ;

举个例子，我们令 $S=$ "abcdefghi"，$k=2$ 。这时$Pr_2=$ "ab"，$Su_2=$ "hi"，翻转后有 $Pr_2=$ "ba"，$Su_2=$ "ih"，那么最终得到的字符串 $S$ 就是 "ihcdefgba"。

这个操作可以被执行许多次（可能是零次），任何一个 $i$ 也可以被使用多次。

我们将字符串 $S$ 和 $T$ 称为相等的字符串，当且仅当存在一个操作序列，将字符串 $S$ 变成 $T$。对于上面的例子来说，"abcdefghi" 和 "ihcdefgba" 是相等的。注意到 $S$ 和它自己也是相等的。

你的任务很简单，数出互不相同的字符串的个数。

最终的答案可能会非常大，因此你只需要输出答案 $mod$ $998244353$ 的结果。

$2 \leq n \leq 10^9$，$1 \leq m \leq min(\frac{n}{2},2 * 10^5)$，$1\leq |A|\leq 10^9$。

有 $n$ 个箱子和 $m$ 个小球，初始时第 $i$ 个箱子有 $a_i$ 个小球。每次操作可以将一个小球移到相邻的箱子里。求要使得最终数组 $a_i\ge a_{i+1}$ 的最小操作次数。

$1\le n,m\le 250$。