时间限制：1000MS 内存限制：131072KB
难度：6.5
给出一张 n 个点的有向图 G(V, E) 。对于任意两个点 u, v （u 可以等于 v ），u 向 v 的连边数为：\sum\limits_{i=1}^k {out[u, i] \times in[v, i]} 。
给定 k 和数组 out, in ，现在有 m 个询问，每次询问给出三个参数 u, v, d，你需要回答从节点 u 出发，经过不超过 d 条边到达节点 v 的路径有多少种。
答案对 10^9+7 取模。
第一行两个整数 n, k 。
接下来 n 行，第 i 行有 2k 个整数，前 k 个整数描述 out[i][]，后 k 个数描述 in[i][] 。
接下来一行一个整数 m 。
接下来 m 行，每行三个整数 u, v, d，描述一组询问。
对于每个询问，输出一个方案数。由于答案可能太大，输出其除以 10^9+7 后的余数。…
时间限制：1000MS 内存限制：131072KB
出题人：chj2001 难度：5.4
存在 n 种物品，其中第 i 种物品的价值为 a_i ，最多可以用 b_i 件，求从这些物品中选取若干件（不能为 0 件），得到的总价值为 9 的倍数的方案。
需要分别计算每种物品中，每件之间有区别的方案数和没有区别的方案数。
（即每种物品按照 1,2,3, \cdots ,b_i 编号的方案数和不编号的方案数。）
第一行输入一个数 n 。
接下来 n 行，每行两个数 a_i, b_i 。
输出共两行，每行各包括一个数，分别表示对于每种物品视为不同的时的方案数和视为相同的时的方案数。有的时候方案数可能很大，你需要将它对 10^9+7 取模。
方案数均不考虑顺序，如 2, 3, 4 和 4, 3, 2 是同一种方案。
如果无法做到则输出 0 。
不考虑同种物品之间的区别，一共有 2 种不同的方案凑出 9 的倍数，即 3, 2, 2, 2 和 3, 3, 3 。
考虑同种和果子的区别时，一共有 C_3^1 \times C_3^3 = 3 种不同的方案凑出 3, 2, 2, 2，C_3^3=1 种方案凑出 3, 3, 3，因此总共有 4 种方案。
对于 40\% 的数据，n \le 1000 , a_i \le 100 , b_i \le 100 。
对于 100\% 的数据，\(1 \le n \le 10^5 , 1 \le a_i \le 90000 , 1 \le b_i \le …
时间限制：5000MS 内存限制：1048576KB
难度：7.0
五福街是一条笔直的道路，这条道路可以看成一个数轴，街上每个建筑物的坐标都可以用一个整数来表示。
小明是一位时光旅行者，他知道在这条街上，在过去现在和未来共有 n 个商店出现。第 i 个商店可 以使用四个整数 x_i , t_i , a_i , b_i 描述，它们分别表示：商店的坐标、商店的类型、商店开业的年份、商店关闭的年份。
小明希望通过时光旅行，选择一个合适的时间，住在五福街上的某个地方。他给出了一份他可能选择的列表，上面包括了 q 个询问，每个询问用二元组 （坐标，时间）表示。第 i 对二元组用两个整数 l_i , y_i 描述，分别表示选择的地点 l_i 和年份 y_i 。
现在，他想计算出在这些时间和地点居住的生活质量。他定义居住的不方便指数为：在居住的年份，离 居住点最远的商店类型到居住点的距离。类型 t 的商店到居住点的距离定义为：在指定的年份，类型 t 的所有营业的商店中，到居住点距离最近的一家到居住点的距离。我们说编号为 i 的商店在第 y 年在营业当且仅当 a_i \leq y \leq b_i 。注意，在某些年份中，可能在五福街上并非所有 k 种类型的商店都有至少一家在营业。在这种情况下，不方便指数定义为 -1。
你的任务是帮助小明求出每对（坐标，时间）二元组居住的不方便指数。
第一行包含三个整数 n,k 和 q ，分别表示商店的数量、商店类型的数量和（坐标，时间）二元组的数量（1 \le n, q \le 3 \times 10^5 , 1 \le k \le n）
接下来 n 行，每行包含四个整数 x_i , t_i , a_i 和 b_i 用于描述一家商店，意义如题面所述 （1 \le x_i , a_i , b_i \le 10^8 , 1 \le t_i \le k, a_i \le b_i）。
接下来 q 行，每行包含两个整数 l_i 和 y_i ，表示一组（坐标，时间）查询 （1 \le l_i , y_i \leq 10^8 ）。
输出一行，包含 q 个整数，依次表示对于 q 组（坐标，时间）询问求出的结果。…
时间限制：1000MS 内存限制：262144KB
难度：8.0
有 N 个 1 \times h[i] 的矩形小棋盘，底边边长为 1，在一条直线上拼成了一个畸形的棋盘。
高度 h[i] 给出，第 i 个矩形的高为 h[i]，例如 h = [3, 2, 4, 2] 的图形如下：
若两个车相互攻击仅当它们在同一列，或在同一行且在这一行它们之间棋盘格子都是存在的，例如上图中 a 与 b 是相互不攻击的，c 与 d，b 与 c 均为相互攻击的。
现在要在这棋盘上放置恰好 K 个相互不攻击的车，问有多少种方案。
输入第 1 行包括两个正整数 N，K，表示了棋盘的列数和放的车数。
第 2 行包含 N 个正整数，表示了棋盘每列的高度。
输出包括一个非负整数，表示有多少种放置的方案，输出答案 \mod 1000000007 后的结果即可。
对于 100\% 的数据，有 N \leq 500，K \leq 500，h[i] \leq 1000000 。
时间限制：1000MS 内存限制：262144KB
难度：5.0
这里有一个关于合法的括号序列的问题。如果插入“+” 和 “1” 到一个括号序列，我们能得到一个正确的数学表达式，我们就认为这个括号序列是合法的。例如，序列 “(())()”, “()” 和 “(()(()))” 是合法的，但是 “)(“, “(()” 和 “(()))(” 是不合法的。我们有一个仅由 “(”，“)” 和 “?” 组成的括号序列，你必须将 “?” 替换成括号，从而得到一个合法的括号序列。
对于给定仅由 “(”，“)” 和 “?” 组成的括号序列，你需要将 “?” 替换成括号，得到一个合法的括号序列，同时需要使得代价之和最小。
文件有多个测试实例（\leq 5）。每个实例的第一行有 1 个正整数 n，（1 \leq n \leq 100000），表示括号序列的长度为 n。第二行是一个长度为 n 的字符串，表示输入的括号序列，字符串仅由 “(”，“)” 和 “?” 组成。接下来 m 行，m 是字符串中 “?” 的个数，每一行包含两个整数 a_i 和 b_i（1 \leq a_i,b_i \leq 1000000），a_i 是将第 i 个 “?” 替换成左括号的代价，b_i 是将第 i 个 “?” 替换成右括号的代价。文件的最后一行有一个 0 表示结束。
将计算出的每个测试实例的答案依次输出到文件中。每个测试实例第一行输出一个整数，表示最小代价和。如果不存在合法方案，输出 -1。如果存在合法方案，第二行输出替换后的括号序列。若有多种替换方案的代价之和最小，可以输出任意一种。…
时间限制：1000MS 内存限制：524288KB
难度： 6.4
小 L 计划进行 n 场游戏，每场游戏使用一张地图，小 L 会选择一辆车在该地图上完成游戏。
小 L 的赛车有三辆，分别用大写字母 A、B、C 表示。地图一共有四种，分别用小写字母 x、a、b、c 表示。其中，赛车 A 不适合在地图 a 上使用，赛车 B 不适合在地图 b 上使用，赛车 C 不适合在地图 c 上使用，而地图 x 则适合所有赛车参加。适合所有赛车参加的地图并不多见，最多只会有 d 张。
n 场游戏的地图可以用一个小写字母组成的字符串描述。例如：S=\underline{\mathrm{xaabxcbc}} 表示小 L 计划进行 8 场游戏，其中第 1 场和第 5 场的地图类型是 x，适合所有赛车，第 2 场和第 3 场的地图是 a，不适合赛车 A，第 4 场和第 7 场的地图是 b，不适合赛车 B，第 6 场和第 8 场的地图是 c，不适合赛车 C 。
小 L 对游戏有一些特殊的要求，这些要求可以用四元组 (i,h_i,j,h_j) 来描述，表示若在第 i 场使用型号为 h_i 的车子，则第 j 场游戏要使用型号为 h_j 的车子。
你能帮小 L 选择每场游戏使用的赛车吗？如果有多种方案，输出任意一种方案。如果无解，输出 “-1”（不含双引号）。
输入第一行包含两个非负整数 n,d 。
输入第二行为一个字符串 S 。
n,d,S 的含义见题目描述，其中 S 包含 n 个字符，且其中恰好 d 个为小写字母 x 。
输入第三行为一个正整数 m，表示有 m 条用车规则。接下来 m 行，每行包含一个四元组 i,h_i,j,h_j ，其中 i,j 为整数，h_i,h_j 为字符 A 、B 或 C，含义见题目描述。
输出一行。
若无解，输出 “-1”（不含双引号）。
若有解，则包含一个长度为 n 的仅包含大写字母 A、B、C 的字符串，表示小 L 在这 n 场游戏中如何安排赛车的使用。如果存在多组解，输出其中任意一组即可。…
时间限制：4000MS 内存限制：262144KB
出题人：E.Space 难度：7.0
它会把输入按行读入，原封不动地复制到输出中去。
但是在一次更新以后，它的程序出了一些问题。
它没法输出换行符了。
并且，读入的时候，总会莫名其妙地随机漏掉开头和结尾的若干个字符，甚至整行都会漏掉。
比如 orzxxxxx 可能会变成 rzxx、orz、x 或者空串。
现在你找到一份输入文件丢给它，你想知道它的输出可能有多少种情况，以及每种情况分别是什么。
由于你找到的输入文件全部来自之前的福建省选，所以所有的输入文件每行只可能包含 A、C、G、T 四种字符。
第一行一个正整数 n，表示（题面中）输入文件的行数。
接下来 n 行，表示输入文件的内容。保证这 n 行中每行的每个字符是 A、C、G、T 四种字符中的一种。
接下来一个整数 k, (0 \leq k \leq 1)，具体含义详见输出格式。
若 k=0，你需要输出一行，表示输出的可能情况个数模 10^9+7 的结果。
若 k=1，你需要按照字典序从小到大输出所有可能的输出情况，一行一个字符串，最后一行输出输出的可能情况个数模 10^9+7 的结果。
时间限制：1000MS 内存限制：262144KB
难度：6.0
给定 2 个长度分别为 m 和 n 的 DNA 序列 X 和 Y，以及一个长度为 p 的模式子序列 P。带有子序列包含约束的最长公共子序列问题就是要找出 X 和 Y 带有包含子序列 P 约束的最长公共子序列的长度。
例如，如果给定的 DNA 序列 X 和 Y 分别为 X=AATGCCTAGGC，Y=CGATCTGGAC，模式子序列 P=GTAC，则子序列 ATCTGGC 是 X 和 Y 的一个无约束的最长公共子序列，而包含 P 为其子序列的最长公共子序列是 GCTAC。
第一行中给出正整数 m,n,p，分别表示给定序列 X 和 Y 以及模式子序列 P 的长度。m,n,p<300 。
接下来的 3 行分别给出序列 X 和 Y 以及模式子序列 P 。
将计算出的 X 和 Y 带有包含子序列 P 约束的最长公共子序列的长度输出。如果 X 和 Y 不存在包含子序列 P 的公共子序列，则输出 -1。
时间限制：1000MS 内存限制：131072KB
难度：5.0
求一个字符串的回文子序列个数。
如果 p_1p_2 \cdots p_m 满足 1 \leq p_1<p_2<\cdots<p_m \leq n，则称 a_{p_1}a_{p_2}\cdots a_{p_m} 是序列 a_1a_2\cdots a_n 的一个子序列。
如果对于所有 1 \leq i \leq n 都满足 a_i=a_n-i+1，则 a 是一个回文串。空串也是回文串。
一个字符串
回文子序列个数 \mod 10^9+7
样例中所有回文子序列按照字典序如下：
“”（空串）、”a”、”aa”、”aka”、”f”、”ff”、”k”、”kak”、”kk”、”t”
对于 100\% 的数据，n \leq 5000 。
字符串中仅包含小写字母。
…