title: [COCI2017-2018#1] Tetris

description:
Ivica is a passionate computer scientist. He recently started working on his first computer game: a clone of the popular Tetris. Although he’s far from being finished, his program supports placing five different Tetris figures shown in the image below in a matrix. Before placing it in the Tetris matrix, the figure can be rotated by 90 degrees an arbitrary number of times and coloured. Additionally, the current version of the game doesn’t support placing the figure if that would mean it goes out of the matrix boundaries or overlaps with another existing figure in the matrix.

![](https://cdn.luogu.com.cn/upload/pic/17376.png)

While Ivica was in school, his sister Marica started the game and randomly rotated, coloured and placed the figures in a way that the adjacent figures are coloured differently. Two figures are adjacent if they share a common side or touch in the tip.

When Ivica came back to his computer, he found the game running with the figures his sister placed. He wants to know how many of which figures there are in the Tetris matrix and he is asking you to help him solve this problem while he’s busy with improving the game.

inputFormat:
The first line of input contains positive integers N and M (1 ≤ N, M ≤ 10) that represent the number of rows and columns of the Tetris matrix.

Each of the following N lines contains M characters that represent the matrix. Each character can be ‘.’ (dot) that represents a blank space or a lowercase letter of the English alphabet that represents a part of the figure. Different letters represent different colours, and the parts
of the same figure are coloured the same.

outputFormat:
You must output exactly five rows. The $i^{th}$ line must contain the number of appearances of
the $i^{th}$ figure in the game of Tetris.

translation:
## 题目描述

Ivica是一位激情昂扬的计算机科学家。他最近开始研究他的第一个电脑游戏：流行于当下的俄罗斯方块的克隆。尽管他还远未完成，但他的研究计划却支持将下图中显示的五种不同的俄罗斯方块图形放在一个矩阵中。在将它放入俄罗斯方块矩阵之前，图形可以旋转90度任意次数并着色。此外，当前版本的游戏不支持放置俄罗斯方块图形，如果这意味着它将超出矩阵边界或与矩阵中的另一个现有图形重叠。

![](https://cdn.luogu.org/upload/pic/17376.png)

当Ivica在学校时，他的妹妹Marica开始游戏并随机旋转，着色并放置俄罗斯方块图形，使相邻的那一些俄罗斯方块颜色不同。如果它们在共用一个共同的侧面或两两相触，则两个图形相邻。（PS：【译者注】当然，一个点｛角｝不算）

当Ivica回到他的电脑后，他发现游戏正在运行着他妹妹放置的俄罗斯方块图形。他想知道俄罗斯方块矩阵中有多少数字，他要求你在他忙于改进游戏时帮助他解决这个问题。

## 输入输出格式

### 输入格式：

第一行输入包含正整数N和M（1≤N，M≤10），表示俄罗斯方块矩阵的行数和列数。

以下N行中的每一行包含表示矩阵的M个字符。每个角色都可以是'.' （点）表示空格或英文字母的小写字母，代表图的一部分。不同的字母代表不同的颜色，同一图的部分颜色相同。

### 输出格式：
你必须输出五行。第 $i^{th}$
 行需要包含$i^{th}$
 图中方块的游戏的出现次数。

## 说明

20％的测试样例中，只有一个数字。

在测试案例中，总价值额外增加20％（也就是40%），只会出现两个数字。

在测试案例中，总价值额外增加20％（当然，也就是60%），出现三个数字。

在测试案例中，总价值额外增加20％，（嗯嗯就是80%），会出现前四个数字

![](https://cdn.luogu.org/upload/pic/17377.png)
翻译贡献者UID：118559

samples:
5 7
.c.....
ccdddd.
caabbcc
aabbacc
...aaa.

hint:
In test cases worth 20% of total points, only the first figure will appear.

In test cases worth an additional 20% of total points, only the first two figures will appear.

In test cases worth an additional 20% of total points, only the first three figures will appear.

In test cases worth an additional 20% of total points, only the first four figures will appear.

![](https://cdn.luogu.com.cn/upload/pic/17377.png)


title: [COCI2017-2018#1] Lozinke

type: P

description:
Recently, there has been a breach of user information from the mega-popular social network Secret Network. Among the confidential information are the passwords of all users.

Mihael, a young student who has been exploring computer security lately, found the whole thing really interesting. While experimenting with the social network, he found another security breach! When you input any string of characters that contains a substring equal to the actual password, the login will be successful. For example, if the user whose password is abc inputs one of the strings abc, abcd or imaabcnema, the system will successfully log him in, whereas the login will fail for axbc.

Mihael wants to know how many ordered pairs of different users exist such that the first user, using their own password, can login as the second user.

inputFormat:
The first line of input contains the positive integer N (1 ≤ N ≤ 20 000), the number of users.

Each of the following N lines contains the user passwords. The passwords consist of at least one and at most 10 lowercase letters of the English alphabet.

outputFormat: The first and only line of output must contains the number of ordered pairs from the task.

translation:
【题目描述】

最近，某社交网络平台出现了用户信息的泄露。

Mihal 是一个喜欢探索计算机安全的学生，他发现整个事情非常有趣。在经过一段时间的研究，他发现了一个安全漏洞。当你输入任何字符串时，如果用户的密码在这个字符串中出现， 那么你就可以通过这个字符串成功登录。 例如，如果密码为 abc 的用户输入了一个字符串为 abc 或 abcdde 或 imaabcnema，他将会成功登录，而 axbc 则会登录失败。

现在 Mihal 想知道会出现多少次用户可以用自己的密码成功登录其他用户的情况。

【输入】

输入第一行为正整数 N，表示用户数量。（N<=20000）

接下来 N 行包含 N 个用户的密码，每个密码小写字母组成，长度不超过 10。

【输出】

输出共一行，输出出现用户可以用自己的密码成功登录其他用户的总次数。

【样例3解释】

第一个用户可以成功登录第二个用户，第二个用户可以成功登录第一个用户，第三个用户可以登录第一个用户和第二个用户，总共出现 4 次本用户成功登录其他用户的情况。

hint:
Clarification of the second test case:

The first user can login as the second user, the second user can login as the first, and the third user can login as both the first and the second user.


title: [COCI2017-2018#1] Deda

description:
Little Marica is making up a ~~nonsensical~~ unusual fairy tale and is telling to her grandfather who keeps interrupting her and asking her ~~stupid~~ intriguing questions.

In Marica’s fairy tale, $N$ children, denoted with numbers from $1$ to $N$ by their age (from the youngest denoted with $1$, to the oldest denoted with $N$), embarked on a train ride. The train leaves from the station $0$ and stops in order at stations $1, 2, 3 \dots$ to infinity.

Each of the following Marica’s statements is of the form: “$At\  stop\ X, child\ A\ got\ out$”, where the order of these statements is completely arbitrary. In other words, it does not depend on the station order. Her grandfather sometimes asks a question of the form: “$\textit{ Based on the statements so far, of the children denoted with a number greater than or equal}\allowbreak\textit{ to B, who is the youngest child that rode for Y or less stops?}$” If at the moment the grandfather asks the question it hasn’t been said so far that a child is getting off the train, we assume that the child is riding for an infinite amount of stops.

Marica must give a correct answer to each of her grandfather’s questions, otherwise the grandfather will get mad and go to sleep. The answer must be correct in the moment when the grandfather asks the question, while it can change later given Marica’s new statements, but that doesn’t matter. Write a program that tracks Marica’s statements and answers her grandfather’s questions.

inputFormat:
The first line of input contains the positive integers $N$ and $Q$ $(2 \le N, Q \le 2 \times 10^{5})$, the number of children and the number of statements. Each of the following $Q$ lines describes:

- either Marica’s statement of the form `M X A`, where $M$ denotes Marica, and $X$ and $A$ are positive integers $(1 \le X \le 10^{9}, 1 \le A \le N)$ from the task,
- or her grandfather’s question of the form `D Y B`, where $D$ denotes the grandfather, and $Y$ and $B$ are positive integers $(1 \le Y \le 10^{9}, 1 \le B \le N)$ from the task.

All of Marica’s statements correspond to different children and at least one line in the input is her grandfather’s question.

outputFormat: For each grandfather’s question, output the number of the required child in its own line. If no such child exists, output `-1`.

translation:
### 题面描述
小马里卡正在创作一个奇妙的童话故事。她一边编故事，一边讲给她的爷爷听。爷爷可高兴了，于是问了她一些有趣的问题。

在小马里卡的故事中，有 $N$ 个年龄分别为 $1$~$N$ 岁的孩子（最小的为 $1$ 岁，最大的为 $N$ 岁）。有一天，她们一起乘火车出去旅行。铁路线上有好多个车站，分别以 $0, 1, 2, 3 \dots$ 编号。其中第 $0$ 站为始发站，火车每到一个车站都会停下来逗留一段时间。每个孩子都可以在选择自己喜欢的车站下车。

小马里卡喜欢这样讲述她的故事：“在第 $X$ 站，年龄为 $A$ 岁的孩子下车了。”不过小马里卡的习惯非常不好，她讲述故事的顺序是完全随机的。换句话说，$X$ 是不单调的。爷爷知道小马里卡的坏习惯，所以他喜欢时不时问一些有趣的问题来找小马里的麻烦。问题是这样的：“年龄大于等于 $B$ 且在第 $Y$ 站（包含第 $Y$ 站）以前下车的最年轻的小孩是多大？”

小马里卡必须正确回答爷爷的问题，否则爷爷会因生气而睡觉。值得注意的是，小马里卡的答案必须在当时是正确的。虽然小马里卡在随后的讲述中可能会改变问题的答案，但这都是无关紧要的。

小马里卡对自己的坏习惯十分无奈。由于故事的顺序过于杂乱，小马里卡根本无法正确回答爷爷的问题。于是她找到了聪明的你。请帮小马里卡编写一个程序，动态追踪她的讲述，并回答爷爷的问题。

### 输入格式
输入的第一行包含两个正整数 $N,Q\ (2 \le N,Q \le 2 \times 10^{5})$，分别代表孩子的数量和语句的数量。

接下来 $Q$ 行，每行一个语句。语句的格式为 `M X A` 或 `D Y B`，分别代表小马里卡的讲述和爷爷的问题。其中 `M`、`D` 为大写字母，$X$、$Y$、$A$、$B$ $(1 \le X,Y \le 10^{9},1 \le A,B \le N)$ 分别为一个正整数。其意义请见【题面描述】。题目中保证至少有一个 `D`。

### 输出格式
对于每一个问题 `D` 输出一个答案。答案为一个整数。如果爷爷的问题无解，请输出 `-1`。


title: [BJWC2011] 最小三角形

description:
Xaviera 现在遇到了一个有趣的问题。

平面上有 $N$ 个点，Xaviera 想找出周长最小的三角形。

由于点非常多，分布也非常乱，所以 Xaviera 想请你来解决这个问题。

为了减小问题的难度，这里的三角形也包括共线的三点。

inputFormat:
第一行包含一个整数 $N$ 表示点的个数。

接下来 $N$ 行每行有两个整数，表示这个点的坐标。

outputFormat: 输出只有一行，包含一个 $6$ 位小数，为周长最短的三角形的周长（四舍五入）。

hint: 对于所有数据，$3 \leq N \leq 2\times 10^5$


title: [HNOI/AHOI2018] 寻宝游戏

description:
某大学每年都会有一次 Mystery Hunt 的活动，玩家需要根据设置的线索解谜，找到宝藏的位置，前一年获胜的队伍可以获得这一年出题的机会。

作为新生的你，对这个活动非常感兴趣。你每天都要从西向东经过教学楼一条很长的走廊，这条走廊是如此的长，以至于它被人戏称为 infinite corridor。一次，你经过这条走廊时注意到在走廊的墙壁上隐藏着 $n$ 个**等长的**二进制的数字，长度均为 $m$。你从西向东将这些数字记录了下来，形成一个含有 $n$ 个数的二进制数组 $a_1,a_2,...,a_n$。

很快，在最新的一期的 Voo Doo 杂志上，你发现了 $q$ 个长度也为 $m$ 的二进制数 $r_1,r_2,...,r_q$。

聪明的你很快发现了这些数字的含义。

保持数组 $a_1,a_2,...,a_n$ 的元素顺序不变，你可以在它们之间插入 $\land$（按位与运算）或者 $\lor$（按位或运算）。例如：$11011\land 00111=00011$，$11011\lor 00111=11111$。

你需要插入 $n$ 个运算符，相邻两个数之前恰好一个，在**第一个数的左边**还有一个。**如果我们在第一个运算符的左边补入一个 0**，这就形成了一个运算式，我们可以计算它的值。与往常一样，运算顺序是**从左到右**。有趣的是，出题人已经告诉你这个值的可能的集合—— Voo Doo 杂志里的那些二进制数 $r_1,r_2,...,r_q$，而解谜的方法，就是对 $r_1,r_2,...,r_q$ 中的每一个值 $r_i$，分别计算出**有多少种方法填入这 $n$ 个计算符**，使的这个运算式的值是 $r_i$。

然而，infinite corridor 真的很长，这意味着数据范围可能非常大。因此，答案也可能非常大，但是你发现由于谜题的特殊性，你只需要求答案模 $1000000007$ 的值。

inputFormat:
第一行三个数 $n,m,q$，含义如题所述。

接下来 $n$ 行，其中第 $i$ 行有一个长度为 $m$ 的二进制数，**左边是最高位**，表示 $a_i$。

接下来 $q$ 行，其中第 $i$ 行有一个长度为 $m$ 的二进制数，**左边是最高位**，表示 $r_i$。

outputFormat: 输出 $q$ 行，每行一个数，其中的 $i$ 行表示对于 $r_i$ 的答案。


title: [HNOI/AHOI2018] 转盘

description:
一次小 G 和小 H 准备去聚餐，但是由于太麻烦了于是题面简化如下：

一个转盘上有摆成一圈的 $n$ 个物品（编号 $1\sim n$），其中的 $i$ 个物品会在 $T_i$ 时刻出现。

在 $0$ 时刻时，小 G 可以任选 $n$ 个物品中的一个，我们将其编号为 $s_0$。并且如果 $i$ 时刻选择了物品 $s_i$，那么 $i+1$ 时刻可以继续选择当前物品或选择下一个物品。当 $s_i$ 为 $n$ 时，下一个物品为物品 $1$，否则为物品 $s_{i}+1$。在每一时刻（包括0时刻），如果小 G 选择的物品已经出现了，那么小 G 将会标记它。小 H 想知道，在物品选择的最优策略下，小 G 什么时候能标记所有物品？

但麻烦的是，物品的出现时间会不时修改。我们将其描述为 $m$ 次修改，每次修改将改变其中一个物品的出现时间。每次修改后，你也需求出当前局面的答案。对于其中部分测试点，小 H 还追加了强制在线的要求。

inputFormat:
第一行三个非负整数 $n$、$m$、$p$，代表一共有 $n$ 个物品，$m$ 次修改。$p$ 只有 $0$ 或 $1$ 两种取值，强制在线时 $p$ 为 $1$，否则 $p$ 为 $0$。

接下来一行，有 $n$ 个**非负整数**，第 $i$ 个数 $T_i$ 代表物品 $i$ 的出现时间。

接下来 $m$ 行，每行两个非负整数 $x$、$y$，代表一次修改及询问。修改方式如下：

1. 如果 $p=0$，则表示物品 $x$ 的出现时间 $T_x$ 修改为 $y$。

2. 如果 $p=1$，则先将 $x$ 和 $y$ 分别异或 $LastAns$，得到 $x'$ 和 $y'$，然后将物品 $x'$ 的出现时间 $T_{x'}$ 修改为 $y'$。其中的 $LastAns$ 是前一个询问的结果；特别的，第一次修改时 $LastAns$ 为初始局面的答案。

保证输入合法。

outputFormat:
第一行一个整数，代表初始局面的答案。

接下来 $m$ 行每行一个整数，分别代表每次修改后的答案。


title: [HNOI/AHOI2018] 毒瘤

description:
从前有一名毒瘤。

毒瘤最近发现了量产毒瘤题的奥秘。考虑如下类型的数据结构题：给出一个数组，要求支持若干种奇奇怪怪的修改操作（比如区间加一个数，或者区间开平方），并支持询问区间和。毒瘤考虑了 $n$ 个这样的修改操作，并编号为 $1\sim n$。当毒瘤要出数据结构题的时候，他就将这些修改操作中选若干个出来，然后出成一道题。

当然了，这样出的题有可能不可做。通过精妙的数学推理，毒瘤揭露了这些修改操作的关系：有 $m$ 对“互相排斥”的修改操作，第 $i$ 对是第 $u_i$ 个操作和第 $v_i$ 个操作。当一道题同时含有 $u_i$ 和 $v_i$ 这两个操作时，这道题就会变得不可做。另一方面，一道题中不包含任何“互相排斥”的修改操作时，这个题就是可做的。此外，毒瘤还发现了一个规律：$m-n$ 是一个很小的数字，且任意两个修改操作都是连通的。两个修改操作 $a,b$ 是连通的，当且仅当存在若干操作 $t_0,t_1,\cdots,t_l$，使得 $t_0=a,t_l=b$，且对 $1\leq i\leq l$，$t_{i-1}$ 和 $t_i$ 都是“互相排斥”的修改操作。

一对“互相排斥”的修改操作称为互斥对。现在毒瘤想知道，给定值 $n$ 和 $m$ 个互斥对，他共能出出多少道可做的不同的数据结构题。两道数据结构题是不同的，当且仅当有一个修改操作在其中一道题中存在，而在另一道题中不存在。

inputFormat:
第一行为正整数 $n,m$。

接下来 $m$ 行，每行两个正整数 $u,v$，代表一对“互相排斥”的修改操作。

outputFormat: 输出一行一个整数，代表毒瘤可以出的可做的不同的“互相排斥”的修改操作的个数。这个数可能很大，所以只输出模 $998244353$ 后的值。

hint:
#### 样例一说明

可做的题包括 $\varnothing,\{1\},\{2\},\{3\},\{1,3\}$。注意，**空集是合法的数据结构题**。

#### 数据范围

![](https://cdn.luogu.com.cn/upload/pic/17511.png)


title: [USACO23JAN] Air Cownditioning II B

description:
With the hottest recorded summer ever at Farmer John's farm, he needs a way to cool down his cows. Thus, he decides to invest in some air conditioners.

Farmer John's $N$ cows $(1 \le N \le 20)$ live in a barn that contains a sequence of stalls in a row, numbered $1 \cdots 100$. Cow $i$ occupies a range of these stalls, starting from stall $s_i$ and ending with stall $t_i$. The ranges of stalls occupied by different cows are all disjoint from each-other. Cows have different cooling requirements. Cow $i$ must be cooled by an amount $c_i$, meaning every stall occupied by cow $i$ must have its temperature reduced by at least $c_i$ units.

The barn contains $M$ air conditioners, labeled $1 \cdots M (1 \le M \le 10)$. The $i$-th air conditioner costs $m_i$ units of money to operate $(1 \le m_i \le 1000)$ and cools the range of stalls starting from stall $a_i$ and ending with stall $b_i$. If running, the $i$-th air conditioner reduces the temperature of all the stalls in this range by $p_i (1 \le p_i \le 10^6)$. Ranges of stalls covered by air conditioners may potentially overlap.

Running a farm is no easy business, so FJ has a tight budget. Please determine the minimum amount of money he needs to spend to keep all of his cows comfortable. It is guaranteed that if FJ uses all of his conditioners, then all cows will be comfortable.

inputFormat:
The first line of input contains $N$ and $M$.

The next $N$ lines describe cows. The ith of these lines contains $s_i, t_i$, and $c_i$.

The next $M$ lines describe air conditioners. The ith of these lines contains $a_i, b_i, p_i$, and $m_i$.

For every input other than the sample, you can assume that $M=10$.

outputFormat: Output a single integer telling the minimum amount of money FJ needs to spend to operate enough air conditioners to satisfy all his cows (with the conditions listed above).

translation:
## 题目描述

农夫约翰的 $N$ 头奶牛 $(1≤N≤20)$ 住在一个谷仓里，谷仓里有连续的牛栏，编号为 $1-100$ 。 奶牛 $i$ 占据了编号 $[s_i,t_i]$ 的牛栏。 不同奶牛占据的牛栏范围是互不相交的。 奶牛有不同的冷却要求，奶牛 $i$ 占用的每个牛栏的温度必须至少降低 $c_i$ 单位。

谷仓包含 $M$ 台空调，标记为 $1-M$ $(1\le M\le10)$。第 $i$ 台空调需要花费 $m_i$ 单位的金钱来运行 $(1\le m_i \le 1000)$ ，如果运行，第 $i$ 台空调将牛栏 $[a_i,b_i]$ 所有牛栏的温度降低 $p_i$（$1\le p_i\le10^6）$。 空调覆盖的牛栏范围可能会重叠。

请帮助农夫约翰求出满足所有奶牛需求要花费的最少金钱。

## 输入格式

第一行两个整数，分别为 $N$ 和 $M$。

第 $2$ 至 $(N+1)$ 行，每行三个整数，分别为 $s_i$、$t_i$ 和 $c_i$ 。

第 $(N+2)$ 至 $(M+N+1)$ 行，每行四个整数， 分别为 $a_i$、$b_i$、$p_i$ 和 $m_i$。

## 输出格式

一个整数，表示最少花费的金钱。

## 提示

### 样例解释 1

一种花费最少的可能解决方案是选择那些冷却区间为 $[2,9]$ 、$[1,2]$ 和 $[6,9]$ 的空调，成本为 $ 3+2+5=10$ .

### 数据范围

对于 $100\%$ 的数据，$1 \le N \le 20$， $1 \le M \le 10$, $ 1 \le a_i, b_i, s_i, t_i \le 100$, $1 \le c_i, p_i \le 10^6$， $1 \le m_i \le 1000$。

hint:
### Explanation for Sample 1

One possible solution that results in the least amount of money spent is to select those that cool the intervals $[2,9], [1,2]$, and $[6,9]$, for a cost of $3+2+5=10$.


title: [BJOI2018] 二进制

description:
pupil 发现对于一个十进制数，无论怎么将其的数字重新排列，均不影响其是不是$3$ 的倍数。他想研究对于二进制，是否也有类似的性质。

于是他生成了一个长为$n$ 的二进制串，希望你对于这个二进制串的一个子区间，能求出其有多少位置不同的连续子串，满足在重新排列后（可包含前导$0$）是一个$3$ 的倍数。

两个位置不同的子区间指开始位置不同或结束位置不同。

由于他想尝试尽量多的情况，他有时会修改串中的一个位置，并且会进行多次询问。

inputFormat:
输入第一行包含一个正整数$n$，表示二进制数的长度。

之后一行$n$ 个空格隔开的整数，保证均是$0$ 或$1$，表示该二进制串。

之后一行一个整数$m$ ，表示询问和修改的总次数。

之后m 行每行为```1 i```，表示pupil 修改了串的第$i$ 个位置（$0$ 变成$1$ 或$1$ 变成$0$ ），或```2 l r```，表示pupil 询问的子区间是$[l,r]$。

串的下标从$1$ 开始。

outputFormat: 对于每次询问，输出一行一个整数表示对应该询问的结果。

hint:
###样例解释

对于第一个询问，区间$[2,2]$ 只有数字$0$，是$3$ 的倍数，区间$[1,3]$ 可以重排成$011_{(2)} = 3_{(10)}$，是$3$ 的倍数，其他区间均不能重排成$3$ 的倍数。

对于第二个询问，全部三个区间均能重排成$3$ 的倍数（注意$00$ 也是合法的）。

###数据范围

对于$20\%$ 的数据，$1 \leq n,m \leq 100$。

对于$50\%$ 的数据，$1 \leq n,m \leq 5000$。

对于$100\%$ 的数据，$1 \leq n,m \leq 100000$，$l \leq r$。


title: [BJOI2018] 染色

description:
pupil 喜欢给图的顶点染颜色。有一天，master 想刁难他，于是给了他一个无重边和自环的无向图，并且对每个点分别给了一个大小为 $2$ 的颜色集合，pupil 只能从这个集合中选一种颜色给这个点染色。master 希望 pupil 的染色方案使得没有两个有边相连的点被染了相同的颜色。

现在 pupil 想知道，是否无论 master 的颜色集合是什么，他均有办法按照要求染色。

inputFormat:
输入包含多组数据。

第一行一个正整数 $T$，表示数据组数。

之后每组数据第一行两个空格隔开的整数 $n,m$，表示这个无向图的点数和边数。

之后 $m$ 行，每行两个空格隔开的正整数 $i,j$，表示图中的一条连接点 $i$ 和点 $j$ 的边。

图的节点从 $1$ 开始标号。

outputFormat: 对于每组数据，如果 pupil 无论如何均能染色，输出一行一个字符串 `YES`，否则输出一行一个字符串 `NO`。

hint:
### 样例解释

对于第一组数据，如果第一个点和第二个点的集合为 $\{A,B\}$，第三个点和第四个点的集合为 $\{A,C\}$，第五个点和第六个点的集合为 $\{B,C\}$，
则奇数点至少使用了两种颜色，偶数点至少使用了两种颜色，因此至少有一个奇数点和一个偶数点颜色相同。但每两个奇数点和每两个偶数点之间均有边，
因此无法满足“没有两个有边相连的点被染了相同的颜色”。

对于第二组数据，无论两个集合是什么，第一个点随便染它的集合中的其中一种颜色，第二个点染它的集合中某个与第一个点不同的颜色即可。

对于第三组数据，如果三个点的集合均是 $\{A,B\}$，那么无法满足“没有两个有边相连的点被染了相同的颜色”。

### 数据范围

- 对于 $10\%$ 的数据，$1 \leq n \leq 3$；
- 对于 $20\%$ 的数据，$1 \leq n \leq 6$；
- 对于 $50\%$ 的数据，$1 \leq n \leq 1000$，$0 \leq m \leq 2000$；
- 对于 $100\%$ 的数据，$1 \leq n \leq 10000$，$0 \leq m \leq 20000$，$1 \leq T \leq 10$。
- 另外存在 5 个不计分的 hack 数据。


title: [BJOI2018] 求和

description: master 对树上的求和非常感兴趣。他生成了一棵有根树，并且希望多次询问这棵树上一段路径上所有节点深度的 $k$ 次方和，而且每次的 $k$ 可能是不同的。此处节点深度的定义是这个节点到根的路径上的边数。他把这个问题交给了 pupil，但 pupil 并不会这么复杂的操作，你能帮他解决吗？

inputFormat:
第一行包含一个正整数 $n$，表示树的节点数。

之后 $n-1$ 行每行两个空格隔开的正整数 $i, j$，表示树上的一条连接点 $i$ 和点 $j$ 的边。

之后一行一个正整数 $m$，表示询问的数量。

之后每行三个空格隔开的正整数 $i, j, k$，表示询问从点 $i$ 到点 $j$ 的路径上所有节点深度的 $k$ 次方和。由于这个结果可能非常大，输出其对 $998244353$ 取模的结果。

树的节点从 $1$ 开始标号，其中 $1$ 号节点为树的根。

outputFormat: 对于每组数据输出一行一个正整数表示取模后的结果。


title: 小猴打架

description:
一开始森林里面有 $N$ 只互不相识的小猴子，它们经常打架，但打架的双方都必须不是好朋友。每次打完架后，打架的双方以及它们的好朋友就会互相认识，成为好朋友。经过 $N-1$ 次打架之后，整个森林的小猴都会成为好朋友。
现在的问题是，总共有多少种不同的打架过程。
比如当 $N=3$ 时，就有 $\{1-2,1-3\}\{1-2,2-3\}\{1-3,1-2\}\{1-3,2-3\}\{2-3,1-2\}\{2-3,1-3\}$ 六种不同的打架过程。

inputFormat: 一个整数 $N$。

outputFormat: 一行，方案数 $\bmod 9999991$。


title: [国家集训队] 航班安排

background:
1. wqs 爱好模拟飞行。
2. clj 开了一家神犇航空，由于 clj 还要玩游戏，所以公司的事务由你来打理。

注意：题目中只是用了这样一个背景，并不与真实 / 模拟飞行相符。

description:
神犇航空有 $K$ 架飞机，为了简化问题，我们认为每架飞机都是相同的。神犇航空的世界中有 $N$ 个机场，以 $0\cdots N-1$ 编号，其中 $0$ 号为基地机场，每天 $0$ 时刻起飞机才可以从该机场起飞，并不晚于 $T$ 时刻回到该机场。

一天，神犇航空接到了 $M$ 个包机请求，每个请求为在 $s$ 时刻从 $a$ 机场起飞，在恰好 $t$ 时刻到达 $b$ 机场，可以净获利 $c$。换言之，你只需要在 $s$ 时刻在 $a$ 机场选择提供一架飞机给请求方，那么这架飞机就会在 $t$ 时刻准时出现在 $b$ 机场，并且你将获得 $c$ 的净利润。

设计一种方案，使得总收益最大。

inputFormat:
第一行，$4$ 个正整数 $N,M,K,T$，如题目描述中所述；

以下 $N$ 行，每行 $N$ 个整数，描述一个 $N\times N$ 的矩阵 $t$，$t_{i,j}$ 表示从机场 $i$ 空载飞至机场 $j$，需要时间 $t_{i,j}$；

以下 $N$ 行，每行 $N$ 个整数，描述一个 $N\times N$ 的矩阵 $f$，$f_{i,j}$ 表示从机场 $i$ 空载飞至机场 $j$，需要费用 $f_{i,j}$；

以下 $M$ 行，每行 $5$ 个整数描述一个请求，依次为 $a,b,s,t,c$。

outputFormat: 仅一行，一个整数，表示最大收益。


title: [国家集训队] 飞行计划

background:
1. wqs喜欢模拟飞行。

2. clj开了一家神犇航空，由于clj还要玩游戏，所以公司的事务由你来打理。

注意：题目中只是用了这样一个背景，并不与真实/模拟飞行相符

description: 神犇航空有一架航班从$A$地飞往$B$地，需要规划一条最经济的飞行线路。为了简化问题，我们认为地面是一个平面，高度为$0$，上有$N$个航路点，有$M$条双向航线，每条航线连接两个航路点，有两个参数$H$和$W$，表示以$h$高度通过这条航路，费用为$(H-h)2+W$。在每个航路点可以爬升/下降高度，每爬升一个高度需要费用$C$，而下降不需要费用。航路点$0$为$A$地，$N-1$为$B$地。

inputFormat:
第一行3个正整数，$N,M$和$C$，含义如题目所述；

以下$M$行，每行4个整数，$u,v,H,W$，表示$u,v$之间有一条航线，$H,W$为描述中的两个参数。

outputFormat: 仅一行，一个整数，表示$A$地到$B$地的最小费用。


title: [COCI2009-2010#1] ALADIN

description:
给你 $n$ 个盒子，有 $q$ 个操作，操作有两种：

- 第一种操作输入格式为 `1 L R A B`，表示将编号为 $L$ 到 $R$ 的盒子里的石头数量变为 $(X-L+1) \times A \bmod B$，其中 $X$ 为盒子的编号。
- 第二种操作输入格式为 `2 L R`，表示查询编号为 $L$ 到 $R$ 的盒子里的石头总数。

inputFormat:
第一行有两个数字 $n$（$1 \leq n \leq 10^9$），$q$ （$1 \leq q \leq 5 \times 10^4$）。

接下来 $q$ 行表示询问操作。

outputFormat: 对于每个第二种操作，输出石头总数。


title: [COCI2017-2018#2] Košnja

description:
Mirko wants to buy land on which he will build a house for his family. So far, he’s seen K pieces of land. Each of them is in the shape of a rectangle and we can think of it as a matrix with N rows and M columns, N × M fields in total.

Mirko is aware that, before construction begins, the property needs to be regularly maintained and the lawn needs to be mowed. Because of this, Mirko bought a lawn mower. In order to mow the entire lawn of N rows and M columns, he needs to go over each field at least once. He can start from any field facing one of the four main directions (up, down, left, and right). His lawn mower can only go forwards (to the adjacent field facing the current direction) or make a 90 degree turn. Additionally, because of his own safety, Mirko can only use the lawn mower on his land, so he cannot leave the matrix.

Since making the lawn mower turn isn’t simple, Mirko wants to mow the lawn with the minimal amount of turns. For each piece of land he saw so far, Mirko wants to know the minimal number of turns he can make so that the entire lawn is mowed. Help Mirko solve this problem.

inputFormat:
The first line of input contains the positive integer K (1 ≤ K ≤ 50 000), the number from the task.

Each of the following K lines contains two positive integers N and M (1 ≤ N, M ≤ 1 000 000), the numbers from the task.

outputFormat: For each piece of land Mirko saw so far, output in a separate line the minimal amount of turns he can take so that the entire lawn is mowed.

translation:
**题目大意：**

给定一个$n*m$的矩阵，每次你可以选择前进一格或转弯（90度），求在不出这个矩阵的情况下遍历全部格点所需最少转弯次数。有多组数据

**输入格式：**

第一行一个整数$k$，表示数据组数

以下$k$行，每行两个整数$n,m$，表示矩阵大小

**输出格式：**

输出一个整数，即最少转弯次数

感谢@守望 提供翻译

hint:
In test cases worth 50% of total points, Mirko will see only one piece of land. The dimensions of this piece of land will be smaller than 500.

**Clarification of the first test case:**

The first piece of land can be mowed without making any turns if he starts from the field in the first column of the table, faced to the right and only going forwards. A similar idea applies for the second piece of land.


title: [COCI2017-2018#2] ZigZag

description:
Zig and Zag are playing a word game. Zig says one letter, and Zag says a word that starts
with that letter. However, the word needs to be from the allowed word list and such that Zag
already said it the least amount of times. If the word choice is ambiguous, then Zag will
choose the one that is lexicographically smaller (sooner in the alphabet). For each Zig’s
letter, it will be possible to choose a word.

Let there be a list consisting of exactly K distinct words and an array of N letters that Zig has
given. Write a program that will, based on the input, output an array of N words that Zag said
during the game.

inputFormat:
The first line of input contains positive integers K (1 ≤ K ≤ 100 000) and N (1 ≤ N ≤ 100 000)
from the task.

Each of the following K lines contains a single word consisting of lowercase letters of the
English alphabet not longer than 21 characters.

Each of the following N lines contains a single lowercase letter of the English alphabet.

outputFormat: You must output N lines, each containing a single word from the task.

translation:
Zig和Zag正在玩文字游戏。Zig说了一个字母，而Zag说了一个以该字母开头的单词。但是这个词需要出现在给出的单词列表中，并且被是相同首字母中使用的次数最少的单词。如果单词的选择不明确(即相同首字母中使用的次数最少的单词不止一个)，那么Zag会选择字典序较小的字母。输入保证对于每个Zig的字母，都有可以选择的单词。

假设有一个由K个不同的单词组成的列表和一个Zig给出的N个字母组成的列表。编写一个程序，根据输入，输出Zag在游戏过程中说出的N个单词。

输入输出格式

输入格式：
第一行输入包含来自的正整数K（1≤K≤100 000）和N（1≤N≤100 000）。

以下K行是K个单词，由小写英文字母组成，不超过21个字母。

以下N行是Zig说的N个小写英文字母。

输出格式：
N行，分别对应N个Zig的询问。

感谢@K_Vin 提供的翻译

samples:
5 3
london
rim
pariz
moskva
sarajevo
p
r
p

hint: In test cases worth 60% of total points, it will hold that N and K are smaller than 500.


title: [COCI2017-2018#2] Usmjeri

description:
We are given a tree with N nodes denoted with different positive integers from 1 to N.
Additionally, you are given M node pairs from the tree in the form of ($a_1$
, $b_1$
), ($a_2$
, $b_2$
), …, ($a_M$
,
$b_M$
).

We need to direct each edge of the tree so that for each given node pair ($a_i$
, $b_i$
) there is a
path from $a_i$
to $b_i$ or from $b_i$
to $a_i$
. How many different ways are there to achieve this?
Since the solution can be quite large, determine it modulo $10^{9}+7$.

inputFormat:
The first line of input contains the positive integers N and M (1 ≤ N, M ≤ $3*10^5$), the number of
nodes in the tree and the number of given node pairs, respectively.

Each of the following N - 1 lines contains two positive integers, the labels of the nodes
connected with an edge.

The $i_{th}$ of the following M lines contains two different positive integers $a_{i}$ and $b_{i}$
, the labels of
the nodes from the $i_{th}$ node pair. All node pairs will be mutually different.

outputFormat:
You must output a single line containing the total number of different ways to direct the
edges of the tree that meet the requirement from the task, modulo $10^{9}+7$.

translation:
给定一颗从1到n编号的n个结点的树

同时给定m个约束，诸如$(a_i,b_i)$

给每一条边定向，使得对于每一对约束对存在一条从$a_i$到$b_i$或从$b_i$到$a_i$的路径。

求可行的方案数，答案对$10^9 + 7$取模

$1 \le n,m \le 3 \times 10^5$

```
给定一颗从1到n编号的n个结点的树

同时给定m个约束，诸如$(a_i,b_i)$

给每一条边定向，使得每一对约束对存在一条从$a_i$到$b_i$或从$b_i$到$a_i$的路径。

求可行的方案数，答案对$10^9 + 7$取模

$1 \le n,m \le 3 \times 10^5$
```

hint:
In test cases worth 20% of total points, the given tree will be a chain. In other words, node i
will be connected with an edge to node i + 1 for all i < N.

In additional test cases worth 40% of total points, it will hold N, M ≤ $5*10^3$.

A tree is a graph that consists of N nodes and N - 1 edges such that there exists a path from each
node to each other node.


title: [COCI2017-2018#2] Garaža

description:
Lately, Slavko’s been studying sequences of natural numbers. He finds a sequence
interesting if the greatest common divisor of all the elements from the sequence is greater
than 1.

Yesterday, he found a sequence consisting of N natural numbers in his garage. Since he
was really bored, he decided to keep himself occupied by asking simple queries. Each query
can be one of the two types:

1. Change the value at position X in the sequence to V.

2. Determine the number of interesting contiguous subarrays contained in the interval
[L, R] of the sequence.

inputFormat:
The first line of input contains the numbers N and Q (1 ≤ N, Q ≤ $10^5$
), representing the
number of elements in the sequence and the number of queries, respectively.

The following line contains N natural numbers $A_i$
(1 ≤ $A_i$ ≤ $10^9$
) that represent the numbers in
the initial sequence.

Each of the following Q lines contains a query of the following form:

 - The first number in the line can be 1 or 2 and represents the type of the query.
 - If the query is of type 1, two numbers follow, X (1 ≤ X ≤ N) and V (1 ≤ V ≤ $10^9$
) from
the task.
 - If the query is of type 2, two numbers follow, L and R (1 ≤ L ≤ R ≤ N) that represent
the left and right interval boundary.

outputFormat:
For each query of type 2, output the number of interesting contiguous subarrays from the
task.

translation: 最近，斯科拉夫一直在研究自然数的序列。如果序列中所有数的最大公约数大于1，他会认为序列很有趣。昨天，他在车库里发现了一个由N个自然数组成的序列。由于他真的很无聊，他决定通过做两种操作使自己有事做 1:将序列中位置X的值更改为V    2：确定序列的区间[L，R]中包含的有趣的连续子阵列的数量

hint:
**Clarification of the first test case:**

The interval from the $2_{nd}$ to the $5_{th}$ position consists of numbers (4, 3, 9, 1). In it, the following are
interesting contiguous subarrays (denoted with square brackets):
**[4]** 3 9 1, 4 **[3]** 9 1, 4 3 **[9]** 1, 4 **[3 9]** 1


title: [HNOI/AHOI2018] 游戏

description:
一次小G和小H在玩寻宝游戏，有 $n$ 个房间排成一列，编号为 $1,2,\cdots,n$ ，相邻的房间之间都有一道门。其中一部分门上锁（因此需要有对应的钥匙才能开门），其余的门都能直接打开。现在小G告诉了小H每把锁的钥匙在哪个房间里（**每把锁有且只有一把钥匙与之对应**），并作出 $p$ 次指示：第 $i$ 次让小H从第 $S_i$ 个房间出发到 $T_i$ 个房间里。但是小G有时会故意在指令中放入死路，而小H也不想浪费多余的体力去尝试，于是想事先调查清楚每次的指令是否会存在一条通路。

你是否能为小H作出解答呢？

inputFormat: 第一行三个数字： $n,m,p$ ，代表有 $n$ 个房间， $m$ 道门上了锁，以及 $p$ 个询问。接下来$m$行，每行两个数字 $x,y$ 代表 $x$ 到 $x+1$ 的钥匙在房间 $y$ 。接下来 $p$ 行，其中第$i$行是两个整数 $S_i$，$T_i$，代表一次询问

outputFormat: 输出 $p$ 行，每行一个`YES`或`NO`，分别代表能或不能到达。

hint:
![](https://cdn.luogu.com.cn/upload/pic/17503.png)

$1\le n,p\le 10^6$ ， $0\le m <n$ ， $1\le x,y,S_i,T_i<n$ 保证 $x$ 不重复


title: 于神之怒加强版

description:
给定 $n,m,k$，计算

$$\sum_{i=1}^n \sum_{j=1}^m \gcd(i,j)^k$$

对 $10^9 + 7$ 取模的结果。

inputFormat:
**本题单测试点内有多组测试数据**。

第一行有两个整数，分别表示数据组数 $T$ 和给定的 $k$。

接下来 $T$ 行，每行两个整数，表示一组数据的 $n$ 和 $m$。

outputFormat: 对于每组数据，输出一行一个整数表示答案。

hint:
#### 数据规模与约定

对于全部的测试点，保证 $1 \leq T \leq 2 \times 10^3$，$1 \leq n, m, k \leq 5 \times 10^6$。


title: [COCI2017-2018#3] Aron

description:
The holiday season is near! Aron wants to get gifts for his friends in Zagreb, so in order to get them on time, he visited a famous toy store in London. After picking out the gifts, he went to the register and discovered that there were already N people in line. Luckily, he noticed that there were groups of people standing in line, in addition to individual customers. A group of people consists of a customer and their friends waiting for them to complete the purchase.
The moment when the customer is done, they and their friends leave the line.

The people considered a group are standing one behind the other and are wearing shirts of matching colour. Two adjacent groups, adjacent individuals or adjacent individual and a group, will never be wearing shirts of the same colour.

Write a program that will, given the data on the people standing in line, output which person in line Aron is.

inputFormat:
The first line of input contains the positive integer N (1 ≤ N ≤ 25) from the task.
Each of the following N lines contains a single character, an uppercase letter of the English alphabet that represents the shirt colour of the $i^{th}$ person in line.

outputFormat: You must output the required number from the task.

translation:
Aron 为了给他的朋友们买礼物正在礼物店排队，它的前面有 $n$ 个人。

但是它发现有些人是在等待他前面的朋友购买，而并非在排队买单。我们认为紧跟在同一个人身后，穿着同样颜色衣服的人是这个人的朋友。一个人的朋友会在这个人购物后随之离开。

现在按照顺序给定排在 Aron 前面的人的衣服的颜色，输出 Aron 还需要等待多少人购物。

hint:
**Clarification of the second test case:**

First in line is the group consisting of two people in red shirts. Second in line is an individual in the blue shirt, third in line is an individual in the red shirt, and fourth in line is a group in green shirts. This makes Aron fifth in line.


title: [COCI2017-2018#3] Programiranje

description: Little Leticija is preparing for a programming exam. Even though she has solved a lot of tasks, there’s one still left unsolved, so she is asking you for help. You are given the word S and Q queries. In each query, you are given positive integers A, B, C and D. Let’s say that word X consists of letters between positions A and B in word S, and word Y from letters between positions C and D in word S. For each query, you must answer if it is possible to somehow rearrange the letters in word Y and obtain word X.

inputFormat:
The first line of input contains the word S (1 ≤ |S| ≤ 50 000). |S| denotes the number of characters in word S, which consists of lowercase letters of the English alphabet. The second line of input contains the positive integer Q (1 ≤ Q ≤ 50 000).

Each of the following Q lines contains four integers A, B, C i D (1 ≤ A ≤ B ≤ |S| and 1 ≤ C ≤ D ≤ |S| ) from the task.

outputFormat: For each query, output “DA” (Croatian for yes) if it is possible, and “NE” (Croatian for no) if it is not.

translation:
Little Leticija 正在准备编程考试。虽然她已经解决了很多任务，但还有一个任务尚未解决，于是她向你寻求帮助。

有一个单词 $S$ 和 $Q$ 次询问。在每次询问中，给出正整数 $A$、$B$、$C$ 和 $D$。假设单词 $X$ 由单词 $S$ 中位置 $A$ 和 $B$ 及其之间的字母组成，而单词 $Y$ 由位置 $C$ 和 $D$ 及其之间的字母组成。您需要回答是否能以某种方式**重新排列单词 $Y$ 中的字母得到单词 $X$**。

**【输入格式】**

第一行输入包含单词 $S$（$1\le\lvert S\rvert\le50000$）。$\lvert S\rvert$ 表示单词 $S$ 中的字符数。$S$ 完全由英文小写字母组成。

第二行输入包含正整数 $Q$（$1\le Q\le50000$）。
以下 $Q$ 行中的每一行包含四个整数 $A$、$B$、$C$ 和 $D$（$1\le A\le B\le\lvert S\rvert$ 且 $1\le C\le D\le\lvert S\rvert$）。

**【输出格式】**

对于每次询问，如果可能，输出`DA`（即克罗地亚语的“是”），如果不可能，则输出`NE`（克语的“否”）。

**【说明/提示】**

对于 $50\%$ 的测试点，有 $1\le\lvert S\rvert\le1000$ 且 $1\le Q\le1000$。

对于 $100\%$ 的测试点，有 $1\le\lvert S\rvert\le50000$，$1\le Q\le50000$，$1\le A\le B\le\lvert S\rvert$ 且 $1\le C\le D\le\lvert S\rvert$。

样例 #3 的解释：在第一次询问中，$X=\tt vovo$，$Y=\tt devo$。在第二次询问中，$X=\tt odev$，$Y=\tt devo$。

hint:
In test cases worth 50% of total points, it will hold: 1 ≤ |S| ≤ 1000 and 1 ≤ Q ≤ 1000.

**Clarification of the third test case:**

In the first query, X=”vovo”, and Y=”devo”. In the second query, X=”odev”, and Y=”devo”.


title: [COCI2017-2018#3] Retro

description:
Little Mirko got a video game console for Christmas. It wasn’t a Playstation 4 or an Xbox one, but Atari 2600, and it came with one free game. The protagonist of the game is standing on the bottom of the screen, and there are various objects dispersed on the rest of the screen, falling towards the bottom.

More precisely, the screen can be represented as a grid of RxS pixels arranged in R rows and S columns. The protagonist takes up one pixel of the lowest line and is marked with ‘M’. The rest of the pixels are marked with some of the characters: ‘.’ (empty space), ‘*’ (bomb), ‘(‘ (open bracket) or ‘)’ (closed bracket).

The protagonist can move one pixel to the left or to the right in a single move, but doesn’t need to, whereas the rest of the objects simultaneously move one pixel down (possibly out of the screen). When the protagonist finds himself at the same position as one of the brackets, we say that he picked up that bracket and added it at the end of his array of acquired brackets. The protagonist’s goal is to acquire the longest possible **valid** bracket
expression.

A valid bracket expression is defined inductively in the following way:

- “()” is a valid expression
- If **a** is a valid expression, then “(**a**)” is a valid expression as well
- If **a** and **b** are valid expressions, then “**ab**” is a valid expression as well

The game ends when the protagonist finds himself at the same position as the bomb, or when all the objects fall out of the screen.

inputFormat:
The first line of input contains the positive integers R and S (1 ≤ R, S ≤ 300) that represent the dimensions of the screen.

Each of the following R lines contains S characters ‘M’, ‘.’, ‘*’, ‘(‘ or ‘)’ that represent the initial state of the screen.

Test data will be such that there will always exist at least one valid bracket expression that is possible to acquire.

outputFormat:
In the first line, you must output the length of the longest valid bracket expression that Mirko can acquire.

In the second line, output that expression. If there are multiple longest valid expressions, output the **lexicographically smallest** one.

translation:
### 题意翻译

Little Mirko 圣诞节获得了一台游戏机，它不是 Playstation 4 也不是 Xbox one，而是一台 Atari 2600，里面自带了一个这样的游戏：主角站在屏幕底部，天上有各种物体掉下来……

准确地说，屏幕可以看做 $R$ 行 $S$ 列的网格，主角站在最后一行，所在的位置标记为 `M`。其他格子上的标记可能是：`.`（空位置），`*`（炸弹），`(`（左括号）或 `)`（右括号）。

主角一次可以向左或向右移动一格，也可以不动，同时其他的物体向下落一格（可以掉出屏幕）。当主角与某括号位置相同时，他就捡起这个括号，放进他的括号序列尾部。游戏的目的是要获得最长的**合法**括号表达式。

合法的括号表达式是按下面方式归纳定义的：

- $\texttt{()}$ 是合法的括号表达式
- 如果 $a$ 是合法的括号表达式，那么 $\texttt{(}a\texttt{)}$ 也是合法的括号表达式。
- 如果 $a$ 和 $b$ 都是合法的括号表达式，那么 $ab$ 也是合法的括号表达式。

当所有物体掉出屏幕或者主角碰到炸弹（与炸弹在相同位置）时游戏结束。

hint:
In test cases worth 25% of total points, it will hold 1 ≤ R ≤ 15.

In test cases worth 50% of total points, it will hold 1 ≤ R ≤ 100.

If you output the correct length, but the wrong expression, you will be awarded 40% of points for that test case. In any case, in order to score points, your output must consist of two non-empty lines. ~~(但我并不会做spj，所以这话屁用没有)~~

**Clarification of the first test case**: The protagonist’s moves are: left, left, right right.

**Clarification of the second test case**: The protagonist’s moves are: stay still, stay still, stay still, right, left.

**Clarification of the third test case**: The protagonist’s moves are: stay still, stay still, right.


title: [COCI2017-2018#3] Portal

description:
The protagonist of this task, Chell, must solve a new puzzle GLaDOS has come up with.

Chell is in a room whose layout that can be represented as a matrix of dimensions N rows and M columns. Each field can be one of the following:

- Obstructed field - there is a wall in it (denoted as ‘#’),
- The field where Chell is initially (denoted as ‘C’),
- The field where Chell must get to in order to solve the puzzle (denoted as ‘F’), or
- An empty field (denoted as ‘.’).

Chell is carrying a so-called portal gun, a gun with which you can create portals in the walls.

In each move, she can do one of the following:
- Move to an adjacent field using one move up, down, left or right (she cannot move to the field with a wall in it). This move lasts one unit of time.
- Create a portal in the wall by turning towards a wall, not necessarily an adjacent one, in the direction up, down, left or right and shooting. The portal will be created only on the side of the wall it was hit from. In each moment, **at most two portals can be active**. If a new portal is being created in the moment when two portals are already active, the one that was created earlier will disappear. It is not possible to create a new portal at the position of another existing portal. This move lasts a negligible
amount of time, i.e. zero amounts of time.
- If she’s at a field that is adjacent to a wall and there’s a portal on her side of the wall, she can step into the portal and exit to a non-obstructed field with another portal. This move is possible if there are two active portals and lasts one unit of time.

Chell wants to know the minimal amount of time it takes for her to solve the puzzle, i.e. to reach the field denoted as ‘F’.

**Please note**: The room will always have walls on the sides, and letters ‘C’ and ‘F’ will appear only once in the matrix.

inputFormat:
The first line of input contains the positive integers N and M (4 ≤ N, M ≤ 500), the numbers from the task.

Each of the following N lines contains M characters that describe the layout of the room.

outputFormat: You must output the minimal amount of time it takes to solve the puzzle, or “nemoguce” (without quotation marks, Croatian for impossible) if it is not possible to solve it.

translation:
题目大意:

给定一个矩阵，每个格子由下列字母表示：

●有障碍的区域表示为‘#’

● 初始位置表示为‘C’

● 目标位置表示为 ‘F’

● 空白区域表示为‘.’

可以进行三种操作：
●走到上下左右相邻的格子，不能走到有墙的区域上，消耗一个单位时间。

●在墙壁上创建传送门，用枪向上、向下、向左，向右直射向着墙壁。传送门会在被击中的墙的一侧产生。在每一时刻，最多两个传送门可以是活动的。如果在已有两个传送门的基础上再射击创建了一个新的，那么较早创建的门将消失。这个射击消耗的时间可忽略。

●如果她在一个靠近墙的地方，墙上有一个传送门，她可以进入，到达另一个门外的无障碍区域出来，需要消耗一个单位时间。

求到达目的地“F”所需的最少时间

hint:
In test cases worth 50% of total points, it will hold 4 ≤ N, M ≤ 15.

**Clarification of the second test case:**

The puzzle can be solved in 8 moves, illustrated in the pictures below.

In the first move, we turn towards the left wall, shoot and create a portal that appears on the wall in the $3^{rd}$ row and $1^{st}$ column (coordinates (3,1)) from the right side.

In the second move, we create a portal from the upper side of the wall at coordinates (6,2).

In the third move, we step into the portal at coordinates (3,1) and exit at coordinates (5,2) - a
non-obstructed field with the second portal.

In the fourth move, we turn right and create a portal from the left side of the wall at coordinates (5,7).
Since there are already two portals, the one at field (3,1) disappears.

In the fifth move, we step into the portal at coordinates (6,2) and exit at coordinates (5,6) with the
second portal.

In the sixth move, we create a new portal from the lower side of the wall at coordinates (1,6), making
the portal at coordinates (6,2) disappear.

In the seventh move, we step into the portal at coordinates (5,7) and exit at coordinates (2,6).
Finally, in the eighth move, we move one place to the right to end the game.

The portal creation in moves 1, 2, 4 and 6 lasts zero amounts of time, whereas the rest of the move
last one unit of time, so the total time needed to solve the puzzle is 4 units of time.

![](https://cdn.luogu.com.cn/upload/pic/17512.png)


title: [COCI2017-2018#3] Dojave

background: 原题每个点4s，但我改不了= =，不过标程1s不到就过了。

description:
The biggest event of the year ended tragically for Croatian teams. The most influential theoretician of CERC of all time, the founder of the popular page CERC Tips, and in his free time an outstanding bass player, in his most recent performance failed to get his team to the finals.

In order to get over his existential troubles, our subject is spending time playing games of chance. He is especially interested in the following game:

You are given a positive integer M. Our protagonist sees in front of him a **permutation** of an array of numbers 0, 1, 2, ..., $2^M$- 1.

The computer chooses a **nonempty contiguous subsequence** of the given permutation, which it then lights up over a capital city of one of the countries in Southeastern Europe.

Our confidant, after fighting off tears caused by memories of old times, **must** choose two distinct elements of the permutation and **swap their places**. Our man of the hour wins if and only if the **bitwise XOR** of the numbers in the lit up subsequence after the substitution is **precisely** $2^M$- 1.

Our hero wants to know **the number of contiguous subsequences** the computer can light up so that he can win.

Help our hero overcome his (id)entity crisis so our favourite page can be fully active again.

inputFormat:
The first line of input contains the integer M (1 ≤ M ≤ 20),

The following line contains $2^M$ space-separated numbers that make up a permutation of the array 0, 1, 2, ..., $2^M$- 1.

outputFormat: You must output the total number of contiguous subsequences that a computer can light up so our hero can win.

translation:
给出一个长度为2^M的排列，元素分别是0， 1， 2， ... , 2^M -1。
选择其中某个非空连续子序列，然后允许交换这个排列中某两个不同的数，然后使得这个连续子序列的所有数的按位异或(bitwise XOR)的结果恰好等于2^M-1
求：有多少个连续子序列满足上述条件。

hint:
In test cases worth 50% of total points, it will hold 1 ≤ M ≤ 14.

**Clarification of the test cases:**

In the first test case, if the computer chooses the subsequence [1 2 3], our hero can replace the numbers 0 and 3. In this case, he can actually win for every chosen contiguous subsequence, except the entire array.

In the second test case, if the computer chooses the entire array [3 7 0 4 6 1 5 2] as the lit up subsequence, our hero can’t change the XOR of the subsequence (which is 0), no matter which two elements are swapped.


title: [COCI2017-2018#3] Sažetak

description:
An unknown array x consists of N integers. The K-summary of that array is obtained by dividing the array into segments of length K and summing up the elements in each segment.
If N is not divisible by K, the last segment of the division will have less than K elements.

In other words, the K-summary is an array where the elements are, respectively: (x[1] + … + x[K]), (x[K+1] + … + x[2K]), and so on, where the last sum that contains x[N] can have less than K summands. For example, the 5-summary of an array of 13 elements has three elements (sum of elements 1.-5., sum of elements 6.-10., sum of elements 11.-13.).

It is clear that we cannot reconstruct the elements of the original array from the K-summary, but that might be possible if we knew several K-summaries for different Ks. Write a program that will, given length N and set $K_1$, $K_2$
, …, $K_M$ , predict how many elements of the original array we would be able to uniquely determine if we knew all the $K_i$ -summaries of the array.
(It is not difficult to show that the number of reconstructed elements is independent of the content of the summaries.)

inputFormat:
The first line contains the integers N and M (3 <= N <= $10^9$
, 1 <= M <= 10), the array length and the number of K-summaries.

The second line contains distinct integers$K_1$, $K_2$ , …, $K_M$
(2 <= $K_i$ < N) from the task.

outputFormat: You must output the required number of reconstructed elements

translation:
### 题目描述

有一个长度为 $N$ 的未知数组 $x$。这个数组的 $K$-总和定义为将该数组分割为若干长度为 $K$ 的区间，并对每个区间中的元素分别求和的结果。如果 $N$ 不能被 $K$ 整除，则最后一个区间的元素数将少于 $K$。

换言之，$K$-总和指的是一个数组，其中的元素分别为：$(x_1+\dots+x_K)$，$(x_{K+1}+\dots+x_{2K})$，以此类推；其中包含了 $x_N$ 的元素，即最后一个元素，可以由少于 $K$ 个部分组成。例如，一个含有十三个元素的数组的 $5$-总和有三个元素（第一到第五项之和，第六到第十项之和，第十一到第十三项之和）

可以发现我们无法通过一个 $K$-总和来重现原数组，但当我们知道几个 $K$ 值不同的 $K$-总和时就有可能做到这一点。给定 $N$ 和 $K_1,K_2,\dots,K_M$，请您编写一条程序，计算在已知一个长为 $N$ 的数组的 $K_i$-总和的前提下，有多少原数组的元素可以被唯一确定（不难发现唯一确定的元素数与 $K_i$-总和的内容无关）。

### 输入格式

第一行包含两个整数 $N$ 和 $M$，$N$ 为原数组大小，$M$ 为已知 $K$-总和的数量。

第二行包含 $M$ 个整数，分别为 $K_1,K_2,\dots,K_M$，如题所述。

### 输出格式

您需要输出唯一确定的元素数。

### 数据范围

对于 $40\%$ 的数据，$N\le5\times10^6$。

对于 $100\%$ 的数据，$3\le N\le10^9$，$1\le M\le10$，$2\le K_i<N$。

### 样例解释

对于第一个样例：我们可以确定 $x_3$。

对于第二个样例：我们可以确定 $x_3$ 和 $x_4$。

翻译来自于 @阿丑

hint:
In test cases worth 40% of total points, it will hold N <= 5 000 000.

**Clarification of the first example**: We can determine one element: x[3].

**Clarification of the second example**: We can determine x[3] and x[4].


title: 双亲数

description:
小 D 是一名数学爱好者，他对数字的着迷到了疯狂的程度。

我们以 $d = \gcd(a, b)$ 表示 $a, b$ 的最大公约数，小 D 执著的认为，这样亲密的关系足可以用双亲来描述，此时，我们称**有序**数对 $(a, b)$ 为 $d$ 的双亲数。

与正常双亲不太相同的是，对于同一个 $d$，他的双亲太多了。

比如，$(4, 6)$，$(6, 4)$，$(2, 100)$ 都是 $2$ 的双亲数。

于是一个这样的问题摆在眼前，对于 $1 \leq a \leq A$，$1 \leq b \leq B$，有多少**有序**数对 $(a, b)$ 是 $d$ 的双亲数？

inputFormat: 输入只有一行三个整数，分别表示 $A, B, d$。

outputFormat: 输出一行一个整数表示答案。


title: [国家集训队] 整数的lqp拆分

background: 来源：2011中国国家集训队命题答辩

description:
lqp在为出题而烦恼，他完全没有头绪，好烦啊…

他首先想到了整数拆分。整数拆分是个很有趣的问题。给你一个正整数 $N$ ，对于N的一个整数拆分就是满足任意 $m>0$，$a_1 ,a_2 ,a_3…a_m>0$，且 $a_1+a_2+a_3+…+a_m=n$ 的一个有序集合。通过长时间的研究我们发现了计算对于 $n$ 的整数拆分的总数有一个很简单的递推式，但是因为这个递推式实在太简单了，如果出这样的题目，大家会对比赛毫无兴趣的。

然后 lqp 又想到了斐波那契数。定义 $F_0=0,F_1=1,F_n=F_{n-1}+F_{n-2} (n>1)$，$F_n$就是斐波那契数的第$n$项。但是求出第 $n$ 项斐波那契数似乎也不怎么困难…

lqp 为了增加选手们比赛的欲望，于是绞尽脑汁，想出了一个有趣的整数拆分，我们暂且叫它：整数的lqp拆分。

和一般的整数拆分一样，整数的 lqp 拆分是满足任意 $m>0$，$a_1 ,a_2 ,a_3…a_m>0$，且 $a_1+a_2+a_3+…+a_m=n$ 的一个有序集合。但是整数的lqp拆分要求的不是拆分总数，相对更加困难一些。

对于每个拆分，lqp 定义这个拆分的权值 $F_{a_1}F_{a_2}…F_{a_m}$，他想知道对于所有的拆分，他们的权值之和是多少？

简单来说，就是求
$\sum\prod_{i=1}^m F_{a_i}$
$m>0$
$a_1,a_2...a_m>0$
$a_1+a_2+...+a_m=n$
由于答案可能非常大，所以要对 $10^9 + 7$ 取模。

inputFormat: 输入的第一行包含一个整数 $n$。

outputFormat: 输出一行一个整数表示答案。


title: [BJOI2018] 双人猜数游戏

background: 本题为提交答案题。可在「附件」中下载输入文件。

description:
Alice 和 Bob 是一对非常聪明的人，他们可以算出各种各样游戏的最优策略。现在有个综艺节目《最强大佬》请他们来玩一个游戏。主持人写了三个正整数 $s$ 、$m$ 、$n$ ，然后一起告诉 Alice 和 Bob $s \leq m \leq n$ 以及 $s$ 是多少。（即，$s$ 是接 下来要猜的 $m$ 、$n$ 的下限。）之后主持人单独告诉Alice $m$ 与 $n$ 的乘积是多少， 单独告诉 Bob $m$ 与 $n$ 的和是多少。

当然，如果一个人同时知道 $m$ 与 $n$ 的乘积以及 $m$ 与 $n$ 的和话就能很容易地算出 $m$和 $n$分别是多少，但现在 Alice 和 Bob只分别知道其中一个，而且只分别知道其中一个，而且他们只能回答主持人的问题，不能交流。从 Alice 或 Bob（见输入）开始 依次询问 Alice/Bob知不知道 $m$ 和
 $n$ 分别是多少， Alice/Bob 只能回答知道/不知道。

为了节目效果，为了显示出Alice 和 Bob 非常聪明，主持人希望Alice 和 Bob 一共说了 $t$次“不知道 ”以后两个人都知道 $m$ 和 $n$ 是多少了 。现在主持人找到你，希望让帮他构造一组符合条件的 $m$ 和 $n$ 。

inputFormat:
共一行，格式为 `s <name> t` （不含引号），其中 $s$ 与 $t$
的定义见题目描述（注意 Alice 和 Bob 知道 $s$ 是多少），<name> 为 “Alice” 或
“Bob” （不含引号），表示主持人第一次问的人。

outputFormat: 共一行两个数，以一个空格隔开，表示一组满足要求的 $m$ 和 $n$。若有多组解，输出 $m$ 与 $n$ 的和最小的那组解。若仍有多组解，输出 $m$ 与 $n$ 的和最小的解中 $m$ 最小的那组解。输入数据保证有解。

samples:
2 Alice 3
4 4

hint:
【样例1说明】

主持人告诉 Alice 和 Bob $5 \leq m \leq n$ ，单独告诉 Alice $mn = 60$ ，单独告诉 Bob $m + n = 16$。

主持人问 Bob知不知道 $m$ 和 $n$ 分别是多少， Bob说不知道。

主持人问 Alice知不知道 $m$ 和 $n$ 分别是多少， Alice说不知道。

主持人问 Bob知不知道 $m$ 和 $n$ 分别是多少， Bob说知道。

主持人问 Alice知不知道 $m$ 和 $n$ 分别是多少， Alice说知道。

【样例2说明】

主持人告诉 Alice 和 Bob $2 \leq m \leq n$ ，单独告诉 Alice $mn = 16$ ，单独告诉 Bob $m + n = 8$。

主持人问 Alice知不知道 $m$ 和 $n$ 分别是多少， Alice说不知道。

主持人问 Bob知不知道 $m$ 和 $n$ 分别是多少， Bob说不知道。

主持人问 Alice知不知道 $m$ 和 $n$ 分别是多少， Alice说不知道。

主持人问 Bob知不知道 $m$ 和 $n$ 分别是多少， Bob说知道。

主持人问 Alice知不知道 $m$ 和 $n$ 分别是多少， Alice说知道。

~~Alice和 Bob分别单独写出了正确的 $m$ 和 $n$ ，观众们觉得 Alice 和 Bob很厉害~~

【数据规模与约定】

对于 $40\%$ 的数据， $t = 2$；

对于 $100\%$ 的数据， $1 \leq s \leq 200$，$2 \leq t \leq 15$，输入数据保证有解。


title: [BJOI2018] 链上二次求和

description:
有一条长度为 $n$ 的链（ $\forall 1 \leq i < n$ ，点 $i$ 与点 $i+1$ 之间有一条边的无向图）， 每个点有一个整数权值，第 $i$ 个点的权值是 $a_i$ 。现在有 $m$ 个操作，每个操作如下：

操作 1（修改）：给定链上两个节点 $u,v$ 和一个整数 $d$，表示将链上 $u$ 到 $v$ 唯一的简单路径上每个点权值都加上 $d$。

操作 2（询问）：给定两个正整数 $l,r$，表示求链上所有节点个数大于等于 $l$ 且小于等于 $r$ 的简单路径节点权值和之和。由于答案很大，只用输出对质数 $1000000007$ 取模的结果即可。

一条节点个数为 $k$ 的简单路径节点权值和为这条上所有 $k$ 个节点（包括端点）的权值之和，而本题中要求是对所有满足要求的简单路径，求这一权值和的和。

由于是无向图，路径也是无向的，即点 $1$ 到点 $2$ 的路径与点 $2$ 到点 $1$ 的路径是同一条，不要重复计算。

inputFormat:
输入第一行包含两个正整数 $n,m$，分别表示节点个数和操作次数。

第二行包含 $n$ 个整数，其中第 $i$ 个数 $a_i$ 为第 $i$ 个点的初始权值。

接下来 $m$ 行，每行为 ```1 u v d```或 ```2 l r```的形式，分别表示进行一次操作 1（修改）或操作 2（询问）。

outputFormat: 对于每次询问，输出一行一个整数，表示答案对 $1000000007$ 取模的余数。

hint:
### 样例解释：
节点个数为 $5$ 的简单路径只有 $1$ 条，权值和为 $5$，故第1次询问输出 $5$。

节点个数为 $1$ 的简单路径有 $5$ 条，每条权值和都是 $1$；节点个数为 $2$ 的简单路径有 $4$ 条，每条权值和都是 $2$，故第2次询问输出 $13 $。

在将点 $1$ 和点 $2$ 的权值加 $2$ 后， $5$ 条节点个数为 $1$ 的简单路径权值和分别为 $3$、$3$、$1$、$1$、$1$，故第 3 次询问输出 $9$。

### 数据范围：
记操作 1（修改）的次数为 $m^\prime$。

对于全部数据， 保证 $n \leq 200000$，$m \leq 500000$，$ m^\prime \leq 100000$，$ 0 \leq a_i < 1000000007$。

$1 \leq u \leq n$，$ 1\leq v \leq n$，$ 0 \leq d < 1000000007$，$l \leq r \leq n$。

对于每个数据点的详细规模与约定见下表。

![pic](https://cdn.luogu.com.cn/upload/pic/17580.png)


title: [CQOI2018] 破解D-H协议

background: Diffie-Hellman 密钥交换协议是一种简单有效的密钥交换方法。它可以让通讯双方在没有事先约定**密钥**的情况下，通过**不安全**（可能被窃听）**的信道**确定一个**安全的密钥** $K$，用于加密之后的通讯内容。

description:
假定通讯双方名为 Alice 和 Bob，协议的工作过程描述如下（其中 $\bmod$ 表示取模运算）：

1. 协议规定一个**固定的**质数 $P$，以及模 $P$ 的一个原根 $g$。**$\boldsymbol P$ 和 $\boldsymbol g$ 的数值都是公开的，无需保密。**

2. Alice 生成一个随机数 $a$，并计算 $A=g^a\bmod P$，将 $A$ 通过不安全信道发送给 Bob。

3. Bob 生成一个随机数 $b$，并计算 $B=g^b\bmod P$，将 $B$ 通过不安全信道发送给 Alice。

4. Bob 根据收到的 $A$ 计算出**密钥** $K=A^b \bmod P$，而 Alice 根据收到的 $B$ 计算出 $K=B^a\bmod P$。

5. 双方得到了相同的 $K$，即 $g^{ab} \bmod P$。$K$ 即之后通讯的加密密钥。

可见，这个过程中可能被窃听的只有 $A,B$，而 $a,b,K$ 是保密的。并且根据 $A,B,P,g$ 这 $4$ 个数，不能轻易计算出 $K$，因此 $K$ 可以作为一个安全的密钥。

当然安全是相对的，该协议的安全性取决于数值的大小，通常 $a,b,P$ 都选取数百位以上的大整数以避免被破解。然而如果 Alice 和 Bob 编程时偷懒，为了避免实现大数运算，选择的数值都小于 $2^{31}$，那么破解他们的密钥就比较容易了。

$T$ 次给定窃听得到的 $A,B$，你需要尝试破解出**密钥** $K$。

inputFormat:
输入文件第一行包含两个空格分开的正整数 $g$ 和 $P$。

第二行为一个正整数 $n$，表示 Alice 和 Bob 共进行了 $n$ 次连接（即运行了 $n$ 次协议）。

接下来 $n$ 行，每行包含两个空格分开的正整数 $A$ 和 $B$，表示某次连接中，被窃听的 $A,B$ 的数值。

outputFormat: 输出包含 $n$ 行，每行 $1$ 个正整数 $K$，为每次连接你破解得到的密钥。

hint:
对于 $30\%$ 的数据，$2\le A,B,P\le 1000$；

对于 $100\%$ 的数据，$2\le A,B<P<2^{31}，2\le g<20，1\le n\le 20$。

$\text{Statement fixed by @Starrykiller.}$


title: [CQOI2018] 社交网络

background: 当今社会，在社交网络上看朋友的消息已经成为许多人生活的一部分。通常，一个用户在社交网络上发布一条消息后，他的好友们也可以看见这条消息，并可能转发。转发的消息还可以继续被人转发，进而扩散到整个社交网络中。

description:
在一个实验性的小规模社交网络中我们发现，有时一条热门消息最终会被所有人转发。为了研究这一现象发生的过程，我们希望计算一条消息所有可能的转发途径有多少种。为了编程方便，我们将初始消息发送者编号为 $1$，其他用户编号依次递增。

该社交网络上的所有好友关系是已知的，也就是说对于 $a, b$ 两个用户，我们知道 $a$ 用户可以看到 $b$ 用户发送的消息。注意可能存在单向的好友关系，即 $a$ 能看到 $b$ 的消息，但 $b$ 不能看到 $a$ 的消息。

还有一个假设是，如果某用户看到他的多个好友转发了同一条消息，他只会选择从其中一个转发，最多转发一次消息。从不同好友的转发，被视为不同的情况。

如果用箭头表示好友关系，下图展示了某个社交网络中消息转发的所有可能情况。（初始消息是用户 $1$ 发送的，加粗箭头表示一次消息转发）

![](https://cdn.luogu.com.cn/upload/pic/17549.png)
![](https://cdn.luogu.com.cn/upload/pic/17550.png)
![](https://cdn.luogu.com.cn/upload/pic/17551.png)
![](https://cdn.luogu.com.cn/upload/pic/17552.png)
![](https://cdn.luogu.com.cn/upload/pic/17553.png)
![](https://cdn.luogu.com.cn/upload/pic/17554.png)

答案对 $10^4 + 7$ 取模。

inputFormat:
第一行有一个整数，表示用户的数量 $n$。
第二行有一个整数，表示好友关系数目 $m$。
接下来 $m$ 行，每行两个整数 $a, b$，表示一组好友关系，即用户 $a$ 可以看到用户 $b$ 发送的信息。

outputFormat: 输出一行一个整数表示答案对 $10^4 + 7$ 取模的结果。

hint:
#### 数据规模与约定

- 对于 $30\%$ 的数据，保证 $n \leq 10$。
- 对于 $100\%$ 的数据，保证 $1 \leq n \leq 250$，$1 \leq m \leq n \times (n - 1)$，$1 \leq a, b \leq n$。


title: [CQOI2018] 交错序列

description:
我们称一个仅由0、1构成的序列为”交错序列“，当且仅当序列中没有相邻的1(可以有相邻的0)。例如，000,001,101,都是交错序列，而110 则不是。

对于一个长度为n 的交错序列，统计其中0 和1出现的次数，分别记为x 和y。给定参数a、b,定义一个交错序列的特征值为$x^ay^b$。注意这里规定任何整数的0 次幂都等于1(包括$0^0=1$)。

显然长度为n 的交错序列可能有多个。我们想要知道，所有长度为n 的交错序列的特征值的和，除以m 的余数。(m 是一个给定的质数)

例如，全部长度为3 的交错串为: 000、001、010、100、101。当a=1,b=2 时，可计算:$3^1\times0^2+2^1\times1^2+2^1\times1^2+2^1\times1^2+1^1\times2^2=10$

inputFormat: 输入文件共一行，包含三个空格分开的整数n,a,b 和m。

outputFormat: 输出文件共一行，为计算结果。


title: [CQOI2018] 解锁屏幕

background:
使用过 Android 手机的同学一定对手势解锁屏幕不陌生。 Android 的解锁屏幕由 $3 \times 3$ 个点组成，手指在屏幕上画一条线，将其中一些点连接起来，即可构成一个解锁图案。如下面三个例子所示：

![](https://cdn.luogu.com.cn/upload/pic/17556.png)
![](https://cdn.luogu.com.cn/upload/pic/17557.png)
![](https://cdn.luogu.com.cn/upload/pic/17558.png)

description:
画线时还需要遵循一些规则：
1. 连接的点数不能少于 $4$ 个。也就是说只连接两个点或者三个点会提示错误。
2. 两个点之间的联线不能弯曲。
3. 每个点只能“使用”一次，不可重复。这里的“使用”是指手指划过一个点，该点变绿。
4. 两个点之间的连线不能“跨过”另一个点，除非那个点之前已经被“使用”过。

对于最后一条规则，参见下图的解释。左边两幅图违反了该规则；而右边两幅图（分别为 $ 2 \rightarrow 4 \rightarrow 1 \rightarrow 3 \rightarrow 6$ 和 $ 6 \rightarrow 5 \rightarrow 4 \rightarrow 1 \rightarrow 9 \rightarrow 2$ ）则没有违反规则，因为在“跨过”点时，点已经被使用过了。

![](https://cdn.luogu.com.cn/upload/pic/17566.png)

现在工程师希望改进解锁屏幕，增减点的数目，并移动点的位置，不再是一个九宫格形状，但保持上述画线规则不变。

请计算新的解锁屏幕上，一共有多少满足规则的画线方案。

inputFormat:
输入第一行为一个整数 $n$ ，表示点的数目。

接下来 $n$ 行，每行两个空格分开的整数 $x_i$ 和 $y_i$ ，表示每个点的坐标。

outputFormat: 输出共一行，为题目所求方案数除以 $10^8+7$ 的余数。

hint:
#### 样例解释 1

设 $4$ 个点编号为 $1$ 到 $4$ ，方案有 $1 \rightarrow 2 \rightarrow 3 \rightarrow 4$ ， $2 \rightarrow 1 \rightarrow 3 \rightarrow 4$ ，  $3 \rightarrow 2 \rightarrow 1 \rightarrow 4$ ，  $2 \rightarrow 3 \rightarrow 1 \rightarrow 4$ 以及它们的镜像。

### 数据范围

- 对于 $30\%$ 的数据，$1 \le n \le 10$。
- 对于 $100\%$ 的数据，$-1000 \le x_i ,y_i \le 1000$，$ 1 \le n < 20$。各点坐标不相同。


title: [CQOI2018] 九连环

background:
九连环是一种源于中国的传统智力游戏。如图所示，九个的圆环套在一把“剑”上，并且互相牵连。游戏的目标是把九个圆环全部从“剑”上卸下。

![](https://cdn.luogu.com.cn/upload/pic/17568.png)

description:
圆环的装卸需要遵守两个规则:

1. 第一个(最右边) 环任何时候都可以任意装上或卸下

2. 如果第k 个环没有被卸下，且第k 个环右边的所有环都被卸下，则第k+1个环(第k 个环左边相邻的环) 可以任意装上或卸下

与魔方的千变万化不同，解九连环的最优策略是唯一的。为简单起见，我们以“四连环”为例，演示这一过程。这里用1表示环在“剑”上，0 表示环已经卸下。

初始状态为1111,每步的操作如下:

1. 1101 (根据规则2,卸下第2 个环)

2. 1100 (根据规则1,卸下第1 个环)

3. 0100 (根据规则2,卸下第4 个环)

4. 0101 (根据规则1,装上第1 个环)

5. 0111 (根据规则2,装上第2 个环)

6. 0110 (根据规则1,卸下第1 个环)

7. 0010 (根据规则2,卸下第3 个环)

8. 0011 (根据规则1,装上第1 个环)

9. 0001 (根据规则2,卸下第2 个环)

10. 0000 (根据规则1,卸下第1 个环)

由此可见，卸下“四连环”至少需要10 步。随着环数增加，需要的步数也会随之增多。例如卸下九连环，就至少需要341步。

请你计算，有n 个环的情况下，按照规则，  全部卸下至少需要多少步。

inputFormat:
输入文件第一行，为一个整数m，表示测试点数目。

接下来m行，每行一个整数n。

outputFormat: 输出文件共m行，对应每个测试点的计算结果。


title: [CQOI2018] 异或序列

description: 已知一个长度为 $n$ 的整数数列 $a_1,a_2,\dots,a_n$，给定查询参数 $l,r$，问在 $a_l,a_{l+1},\dots,a_r$ 区间内，有多少子区间满足异或和等于 $k$。也就是说，对于所有的 $x,y (l \leq x \leq y \leq r)$，能够满足 $a_x \oplus a_{x+1} \oplus \dots \oplus a_y = k$ 的 $x,y$ 有多少组。

inputFormat:
输入文件第一行，为 $3$ 个整数 $n,m,k$。

第二行为空格分开的 $n$ 个整数，即 $a_1,a_2,..a_n$。

接下来 $m$ 行，每行两个整数 $l_j,r_j$，表示一次查询。

outputFormat: 输出文件共 $m$ 行，对应每个查询的计算结果。

hint:
对于 $30\%$ 的数据，$1 \leq n, m \leq 1000$。

对于 $100\%$ 的数据，$1 \leq n, m \leq 10^5$，$0 \leq k, a_i \leq 10^5$，$1 \leq l_j \leq r_j \leq n$。


title: [BJOI2018] 治疗之雨

background:
（没玩过《炉石传说》的人可以跳过这一段）今天我们来探讨下《炉石传说》中“治疗之雨”（恢复 $12$ 点生命值，随机分配到所有友方角色上）和“暗影打击装甲”（每当一个角色获得治疗，便对随机敌人造成 $1$点伤害）这两张卡牌之间的互动效果。假设你场上有 $m$个剩余生命值无限大且生命值上限减去剩余生命值也无限大的随从，而对方的场上有 $k$个暗影打击装甲，你的英雄剩余生命值为 $p$、生命值上限为 $n$，现在你使用了一张可以恢复无限多（而不是 $12$ 点）生命值的治疗之雨，问治疗之雨期望总共恢复了几点生命值以后你的英雄会死亡（生命值降为 $0$；治疗之雨的判定机制使得在此后再也不会为英雄恢复生命值）。

注：题目背景与题目描述有冲突的地方请以题目描述为准

下面让我们再形式化地描述一遍问题。

description:
**题目更新：鉴于很多人反映看不懂题，但是出于尊重原题面的原则不进行大幅度更改。您可以将最小值和最大值理解为下限和上限，类似于题目背景中的血量。**

你现在有 $m+1$ 个数：第一个为 $p$，最小值为 $0$，最大值为 $n$；剩下 $m$个都是无穷，没有最小值或最大值。你可以进行任意多轮操作，每轮操作如下：

在不为最大值的数中等概率随机选择一个（如果没有则不操作），把它加一；

进行 $k$次这个步骤：在不为最小值的数中等概率随机选择一个（如果没有则不操作），把它减一。

现在问期望进行多少轮操作以后第一个数会变为最小值 $0$。

inputFormat:
输入包含多组数据。
输入第一行包含一个正整数 $T$，表示数据组数。
接下来 $T$行 ，每行 4个非负整数 $n$、$p$、$m$、$k$（含义见题目描述），表示一次询问。

outputFormat:
输出 $T$行，每行一个整数，表示一次询问的答案。

如果无论进行多少轮操作，第一个数都不会变为最小值 $0$，那么输出```-1```；

否则，可以证明答案一定为有理数，那么请输出答案模 $1000000007$ 的余数，即设答案为 $\frac{a}{b}$（$a$、$b$为互质的正整数 ），你输出的整数为 $x$，那么你需要保证 $0 \leq x < 1000000007$且 $a \equiv bx\ mod\ 1000000007$。

hint:
###数据范围

对于 $10\%$ 的数据， $n \leq 3$ ，$m, k \leq 2$ 。

对于 $20\%$ 的数据， $n, m, k \leq 5$ 。

对于 $30\%$ 的数据， $n, m, k \leq 30$ 。

对于 $40\%$ 的数据， $n, m, k \leq 50$ 。

对于 $50\%$ 的数据， $n, m, k \leq 200$ 。

对于 $70\%$ 的数据， $n \leq 200$ 。

对于 $80\%$ 的数据， $n \leq 500$ 。

对于 $100\%$ 的数据， $1 \leq T \leq 100$，$1 \leq p \leq n \leq 1500$ ，$0 \leq m, k \leq 1000000000$。

保证不存在$n=p=k=1$,$m=0$的情况（因为出题人判错了）

保证不存在答案的分母是$1000000007$的倍数的情况（因为出题人没想到）


title: [集训队互测 2012] calc

description:
一个序列 $a_1,a_2,\dots,a_n$ 是合法的，当且仅当：

- $a_1,a_2,\dots,a_n$ 都是 $[1,k]$ 中的整数。
- $a_1,a_2,\dots,a_n$ 互不相等。

一个序列的值定义为它里面所有数的乘积，即 $a_1\times a_2\times\dots\times a_n$。

求所有不同合法序列的值的和对 $p$ 取模后的结果。两个序列不同当且仅当他们任意一位不同。

inputFormat: 一行三个正整数 $k, n, p$。意义为上面所说的。

outputFormat: 一行结果。

hint:
【数据范围】

对于 $5\%$ 的数据，$k \le 10$，$n \le 10$。

对于 $20\%$ 的数据，$k \le 1000$，$n \le 20$。

对于 $50\%$ 的数据，$k \le 10^9$，$n \le 20$。

对于 $100\%$ 的数据，$k \le 10 ^ 9$，$n \le 500$，$p \le 10 ^ 9$，保证 $p$ 为素数，保证 $n + 1 < k < p$。

by WJMZBMR
****
$\mathsf i \color{red}\mathsf{ostream}$ 觉得这题数据太弱了，于是他造了个[加强版](https://www.luogu.com.cn/problem/P5850)


title: [国家集训队] JZPKIL

description:
给定$ n, x, y$，求

$$\sum_{i=1}^{n}\mathrm{gcd}(i,n)^x \mathrm{lcm}(i,n)^y \bmod (10^9+7)$$

inputFormat:
第一行，询问个数 $T$。

下面 $T$ 行，每行三个整数 $n, x, y$。

outputFormat: $T$ 行，每行一个整数，表示相应的询问的答案


title: [国家集训队] JZPSTR

description:
你要对一个字符串进行三种操作：

0. 在位置$x_i$处插入一个字符串$y_i$

1. 删除位置$[x_i, y_i)$的字符串

2. 查询位置$[x_i, y_i)$的字符串包含多少次给定的子串$z_i$

inputFormat:
第一行，一个整数$T$，表示操作个数。

下面$T$行，每行第一个数$p_i$，表示这个操作的类型：

若$p_i=0$，则接下来有一个整数$x_i$和一个字符串$y_i$，表示进行插入操作；

若$p_i=1$，则接下来有两个整数$x_i$和$y_i$，表示进行删除操作；

若$p_i=2$，则接下来有两个整数$x_i$和$y_i$，以及一个字符串$z_i$，表示进行询问。

字符串的下标从$0$开始(即第一个字符的下标为$0$)。

初始时字符串为空。

对于插入操作，插入后字符串$y_i$的首字符的下标应为$x_i$；

对于删除操作，删除的区间$[x_i, y_i)$为左闭右开区间；

对于查询操作，询问的区间$[x_i, y_i)$为左闭右开区间。

所有插入的和查询的字符串均不为空，且只包含0~9的字符。

所有询问的区间和删除的区间均不为空。

保证输入数据合法。

对于"左闭右开区间"不理解的可以去看样例解释。

outputFormat: 对每个询问操作，输出一行，表示这个询问的答案。

hint:
第一次操作后，字符串为894894894；

第二次操作，询问的区间为89，不包含任何894；

第三次操作，询问的区间为894894894，包含三个894；

第四次操作后，字符串为8964894894；

第五次操作，询问的区间为896489489，包含一个64；

第六次操作，询问的区间为896489489，包含一个894；

第七次操作后，字符串为894894；

第八次操作，询问的区间为894894，包含两个894。

50%的数据中，询问个数<=100 (不是操作个数)

100%的数据中，插入总长度<=2000000，任何时刻字符串长度<=1000000，插入次数<=1001，删除次数<=1000，询问的z_i的总长度<=10000

来源：2012集训队互测，by gyz


title: [国家集训队] 和与积

description:
给出 $n$，统计满足下面条件的数对 $(a,b)$ 的个数：

1. $1\le a<b \le n$。
2. $a+b$ 整除 $a\times b$。

inputFormat: 一行一个整数数 $n$。

outputFormat: 一行一个整数表示答案。


title: [SCOI2007] k短路

description:
有 $n$ 个城市和 $m$ 条单向道路，城市编号为 $1$ 到 $n$。每条道路连接两个不同的城市，且任意两条道路要么起点不同要么终点不同，因此 $n$ 和 $m$ 满足$m \le n(n-1)$。

给定两个城市 $a$ 和 $b$，可以给 $a$ 到 $b$ 的所有简单路（所有城市最多经过一次，包括起点和终点）排序：先按长度从小到大排序，长度相同时按照字典序从小到大排序。你的任务是求出 $a$ 到 $b$ 的第 $k$ 短路。

inputFormat:
输入第一行包含五个正整数 $n,m,k,a,b$。

以下 $m$ 行每行三个整数 $u,v,l$，表示从城市 $u$ 到城市 $v$ 有一条长度为 $l$ 的单向道路。

outputFormat: 如果 $a$ 到 $b$ 的简单路不足 $k$ 条，输出 `No`，否则输出第 $k$ 短路：从城市 $a$ 开始依次输出每个到达的城市，直到城市 $b$，中间用减号 `-` 分割。

hint:
第一个例子有 $5$ 个城市，所有可能出现的道路均存在。从城市 $1$ 到城市 $5$ 一共有 $5$ 条简单路，排序如下：

![](https://cdn.luogu.com.cn/upload/pic/17706.png)

- $20\%$ 的数据满足：$n\leq 5$；
- $40\%$ 的数据满足：$n\leq 30$；
- $100\%$ 的数据满足：$2\leq n\leq 50$，$1\leq k\leq 200$，$1\le l\le 10^4$。


title: [SCOI2007] 折纸

description:
桌上有一张边界平行于坐标轴的正方形纸片，左下角的坐标为(0,0)，右上角的坐标为(100,100)。接下来执行n条折纸命令。每条命令用两个不同点P1(x1,y1)和P2(x2,y2)来表示，执行时把当前的折纸作品沿着P1P2所在直线折叠，并把有向线段P1P2的右边折向左边（左边的部分保持不变）。

折叠结束后，需要在作品上打一个孔，然后用绳子穿起来挂在墙上。孔的位置是相当重要的：若需要穿过太多层的纸，打孔本身比较困难；若穿过的层数太少，悬挂起来以后作品可能会被撕破。为了选择一个比较合适的打孔位置，你需要计算在每个候选位置打孔时穿过的层数。如果恰好穿过某一层的边界（误差0.000001内），则该层不统计在结果中。

本题考虑一个简化的模型：纸的厚度不计，因此折纸操作总能完美执行。

inputFormat:
输入第一行为一个整数n，即折纸的次数。以下n行每行四个实数x1,y1,x2,y2，表示每次折纸时对应的有向线段。

下一行包含一个正整数m，即候选位置的个数，以下每行包含两个实数x,y，表示一个候选位置。

outputFormat: 每个候选位置输出一行，包含一个整数，即该位置打孔时穿过的层数。

hint:
![](https://cdn.luogu.com.cn/upload/pic/17707.png )

20%的数据满足：n<=1

100%的数据满足：0<=n<=8, 1<=m<=50


title: [SCOI2007] 最优驾车

description:
有n条南北方向的双向街道和n条东西方向的双向街道纵横交错。相邻街道（不管是哪个走向）的距离均为L英里。西南角交叉口的坐标为$(1,1)$，东北角为$(n,n)$。在所有交叉口均可任意改变行驶方向。每条街道有它自己的最高速度限制，该限制对整条街道有效（不管行驶方向如何）。

你的任务是从交叉口$(x_s,y_s)$开车行驶到$(x_t,y_t)$，要求只能在交叉口处改变速度，行驶过程中不得违反所在街道的速度限制，只能沿着路程最短的线路行驶，并且行驶时间在给定的闭区间$[t_1,t_2]$内。车速以“每小时英里数”为单位，它必须是$5$的正整数倍。若车速为$v$，则每加仑汽油能行驶的英里数为$80-0.03v^2$。

inputFormat:
输入第一行为两个整数$n, L$。
第二行包含$n$个正整数，从南到北描述$n$条东西走向的街道的速度限制。
第三行包含$n$个正整数，从西到东描述$n$条南北走向的街道的速度限制。
第四行包含六个正整数$x_s, y_s, x_t, y_t, t_1, t_2$。

outputFormat:
如果无解，输出No。

否则输出两行，分别描述最早到达的方案（若有多种方案，选择其中最省油的）和最省油的方案（如果有多种方案，选择其中最早到达的）。每种方案用两个数表示，第一个数表示到达时刻（单位：分钟，向上取整）；第二个数表示耗油量（单位：加仑，四舍五入保留两位小数）。

hint:
样例1的最快路线为以40英里/小时为速度匀速前进，路程为200英里，因此时间为5小时，每加仑汽油可以行驶80-0.03*40*40=32英里，因此耗油量为200/32=6.25加仑。

最省油路线是先以40英里/小时行驶120英里，然后以35英里/小时行驶80英里，耗油量为120/32+80/(80-0.03*35*35)=5.60加仑。下图的路线可以同时满足两种方案（其中第二种方案需要在(6,2)处改变速度）。

![](https://cdn.luogu.com.cn/upload/pic/17708.png )

20%的数据满足：n<=4

50%的数据满足：n<=8

100%的数据满足：1<=n<=10, 1<=l<=20, 0<=t1<=t2<=1000. 速度限制不超过50


title: [BJWC2018] 售票

description:
C 市火车站最近出现了一种新式自动售票机。买票时，乘客要先在售票机上输入终点名称。一共有 $N$ 处目的地，随着乘客按顺序输入终点名称的每个字母，候选终点站数目会逐渐减少。

在自动售票机屏幕上，有一个 $4$ 行 $8$ 列的键盘，如下图所示。

![](https://cdn.luogu.com.cn/upload/pic/17861.png)

在乘客每输入一个字母后，键盘上只有有效字符是可选的（取决于还有哪些候选终点站），其余的字母会被字符 `*` 取代。

告诉你 $N$ 处目的地的名称，以及乘客已经输入的若干字符，请你输出键盘目前的状态。

inputFormat: 第一行为一个整数 $N (1\leq N \leq 50)$。接下来 $N$ 行，每行一个由大写英文字母组成的长度不超过 $100$ 的字符串，表示一处目的地。最后一行，一个长度不超过 $100$ 的字符串，表示按顺序输入的若干字符。

outputFormat: 输出 $4$ 行，每行一个长度为 $8$ 的字符串，表示键盘状态。

hint:
**【样例解释】**

输入 `ZA` 以后，下一个字符可能是 `G`（终点站有可能是 `ZAGREB`），或 `D`（终点站有可能是 `ZADAR`），或 `B`（终点站有可能是 `ZABOK`）。


title: [BJWC2018] 词韵

description:
Adrian 很喜欢诗歌中的韵。他认为，两个单词押韵当且仅当它们的最长公共后缀的长度至少是其中较长单词的长度减一。也就是说，单词A 与单词B 押韵当且仅当LCS(A,B) ≥ max(|A|,|B|)- 1。( 其中LCS 是最长公共后缀longest common suffix 的缩写）

现在，  Adrian 得到了N 个单词。他想从中选出尽可能多的单词，要求它们能组成一个单词序列，使得单词序列中任何两个相邻单词是押韵的。

inputFormat:
第一行是一个整数N。

接下来N 行，每行一个由小写英文字母组成的字符串，表示每个单词。所有单词互不相同。

outputFormat: 输出一行，为一个整数，  表示最长单词序列的长度。

hint:
**【样例解释】**

一种最长单词序列是ask-psk-sk-k。

**【数据规模和约定】**

30%的测试数据：1≤N≤20，所有单词长度之和不超过3 000

100%的测试数据：1≤N≤500000，所有单词长度之和不超过3 000 000。


title: [BJWC2018] 八维

description:
我们将一个 $M$ 行 $N$ 列的字符矩阵无限复制，可以得到一个无限字符矩阵。例如，对于以下矩阵:

$$\begin{aligned}
& \verb!honi! \\
& \verb!hsin! \\
\end{aligned}$$

可以无限复制出矩阵

$$\begin{aligned}
& \verb!...honihonihonihoni...! \\
& \verb!...hsinhsinhsinhsin...! \\
& \verb!...honihonihonihoni...! \\
& \verb!...hsinhsinhsinhsin...! \\
\end{aligned}$$

我们认为矩阵是八连通的。八连通，  指矩阵中的每个位置与上下左右和四个斜向（左上、右上、左下、右下）的位置相邻。因此，从矩阵任意位置出发沿八个方向中的任意一个都可以无限延长。

如果我们随机选择一个位置和一个方向，则可以从此位置开始沿此方向连续选取 $K$ 个字符组成一个字符串。问，两次这样操作得到两个相同字符串的概率是多少。(假设随机选择时任意位置是等可能的，任意方向也是等可能的)

inputFormat:
第一行是三个整数 $M,  N,  K$。

接下来 $M$ 行，  每行一个由小写英文字母组成的长度为 $N$ 的字符串，即 $M\times N$ 的字符矩阵。保证矩阵中至少出现两种不同字符。

outputFormat: 输出一行，为一个化简后的分数，表示概率。

hint:
**【样例解释】**

样例一中，一次操作共有 $16$ 种可能，其中得到 $\verb!aa!$ 的概率是 $1/8$，得到 $\verb!ab!$ 的概率是 $3/8$,得到bb 的概率是 $1/8$，得到 $\verb!ba!$ 的概率是 $\verb!3/8!$。两次操作结果相同的
概率是 $5/16$。

**【数据规模和约定】**

- 对于 $30\%$ 的测试数据：$M, N ≤ 10$，$K ≤ 100$。
- 对于 $50\%$ 的测试数据：$M = N$。
- 对于 $100\%$ 的测试数据 ：$1 ≤ M,N ≤ 500$，$2 ≤ K ≤ 10^9$。


title: 「物理」平抛运动

description:
> 小 F 回到班上，面对自己 28 / 110 的物理，感觉非常凉凉。他准备从最基础的力学学起。

如图，一个可以视为质点的小球在点 $A(x_0, y_0)$ 沿 $x$ 轴负方向以某速度抛出，无视除重力外的所有阻力，最后恰好以速度 $v$ 砸到 $B(0, 0)$ 点。

![A1](https://cdn.luogu.com.cn/upload/pic/17884.png)

给定 $v$ 的大小与方向，你的任务是求出 $(x_0,y_0)$。

给定的速度单位为 $m \cdot s ^ {-1}$，重力加速度 $g = 10 \ (m \cdot s ^ {-2})$，请输出以 $m$ 为单位的答案。

如果你没有学过相关内容也没有关系，你可以从样例和提示里理解该题所求内容。

inputFormat: 输入一行，为两个最多 $6$ 位的小数 $v, \theta(1 \leq v \leq 100, 15 ^ \circ \leq \theta \leq 75 ^ \circ )$，即速度与图中所标角在弧度制下的大小。

outputFormat:
输出一行，两个最多 $15$ 位的小数 $x_0, y_0$，为你的答案。

你的答案与参考答案的相对误差或者绝对误差小于 $10 ^ {-3}$ 即视为正确。

hint:
### 样例解释

如图。

![A2](https://cdn.luogu.com.cn/upload/pic/17887.png )

$14.142136 \approx 10 \sqrt 2, 0.785398 \approx \frac \pi 4 = 45 ^ \circ .$

小球从 $(10, 5)$ 以速度 $(-10, 0)$ 抛出，即可在 $t = 1s$ 时以 $(-10, -10)$ 砸在 $(0, 0)$。

### 提示

如果你没有学习过相关内容，下面的内容可能有帮助：

> zcy 教你学物理

首先，由于单位均为标准单位，所以所有结果均可以直接数字运算；视为质点意味着没有体积。

我们可以将小球速度分解，如图：

![A3](https://cdn.luogu.com.cn/upload/pic/17886.png )

其中水平方向上的速度 $v_x$ 即为抛出速度，运动过程中一直为 $v \sin \theta$；

垂直方向上的速度 $v_y$ 受重力加速，由 $0$ 变化至 $v \cos \theta$。

从抛出时开始计时，当时间为 $t$ 时，设此时水平、垂直方向上速度的大小分别为 $v_{xt}, v_{yt}$，水平、垂直方向上位移的大小分别为 $x_{xt}, x_{yt}$，有：

$v_{xt} = v \sin \theta$

$v_{yt} = gt$

$x_{xt} = v_{xt}t$

$x_{yt} = \frac 1 2 g t ^ 2 = \frac 1 2{v_{yt}t}$

当 $t$ 恰好是落地时间时，$x_{xt}, x_{yt}$ 即为答案。

---

关于弧度制：

$\pi = 180 ^{\circ}$

也就是说：$\frac \pi 2 = 90 ^{\circ}, \frac \pi 3 = 60 ^{\circ}, \ \cdots $

---

关于三角函数：

如果你是 C/C++ 选手，你可以使用 `math.h` /  `cmath` 里的 `sin()` `cos()` 进行计算；

如果你是 Pascal 选手，你可以使用 `math` 库（在 `begin` 前添加 `uses math;`）里的 `sin()` `cos()` 进行计算。

如果你是 Python 选手，你可以使用 `math` 库里的 `math.sin()` `math.cos()` 进行计算。

如果你是其他语言的选手，请参考相应文档。


title: 「化学」相对分子质量

description:
做化学题时，小 F 总是里算错相对分子质量，这让他非常苦恼。

小 F 找到了你，请你来帮他算一算给定物质的相对分子质量。

如果你没有学过相关内容也没有关系，你可以从样例和提示里理解该题所求内容。

inputFormat:
输入一行，为一个长度为 $L$ $(L\leq 100)$ 的不含空格的字符串，表示给定物质的化学式。

化学式仅包括以下内容:

* 元素：如 `Au`(金)，`Hf`(铪)，**出现的所有元素及其相对原子质量以附表为准**。
* 下标 `_{}` ：表示某个原子、离子或者原子团的个数，如 `H_{2}O` 表示 $H_2O$ (水)，`C_{60}` 表示 $C_{60}$ (足球烯)。
* 括号 `()`：表示一个原子团，下标对团内物质生效。如 `Ca(OH)_{2}` 表示 $Ca(OH)_2$ (熟石灰)。
* 水合物 `~`：如 `CuSO_{4}~5H_{2}O` 表示 $CuSO_4 \cdot 5H_2O$（胆矾）。水之前如果存在数字，保证一定是大于 $2$ 的正整数，如果省略该部分则默认为 $1$ 。如上述胆矾中，表示水的个数的 `5`。

形式化地讲，你处理的化学式满足以下规则：

> 分子`~`数量`H_{2}O`

其中数量或水合部分可省。

对于分子，满足：

> 部分`_{`数量`}`部分`_{`数量`}`...部分`_{`数量`}`

其中数量可省。

对于每个“部分”（原子，原子团，离子……），满足：

> 元素

或

> `(`元素`_{` 数量 `}`元素`_{` 数量`}`... 元素`_{`数量`})`

其中数量可省。

请注意，满足上述条件的化学式不会出现括号嵌套；上文中出现的 “数量” 所指代的数字不超过 $10000$。

outputFormat:
输出一行，包含一个整数或者小数部分为 `.5` 的实数，为你的计算结果。

保证结果不超过 $10000$。


title: [国家集训队] 飞飞侠

background: 来源：国家集训队 2011 何朴藩

description:
飞飞国是一个传说中的国度，国家的居民叫做飞飞侠。飞飞国是一个 $N\times M$ 的矩形方阵，每个格子代表一个街区。

然而飞飞国是没有交通工具的。飞飞侠完全靠地面的弹射装置来移动。

每个街区都装有弹射装置。使用弹射装置是需要支付一定费用的。而且每个弹射装置都有自己的弹射能力。

我们设第 $i$ 行第 $j$ 列的弹射装置有 $A_{i,j}$ 的费用和 $B_{i,j}$ 的弹射能力。并规定有相邻边的格子间距离是 $1$。那么，任何飞飞侠都只需要在 $(i,j)$ 支付 $A_{i,j}$ 的费用就可以任意选择弹到距离不超过 $B_{i,j}$ 的位置了。如下图
![https://cdn.luogu.com.cn/upload/pic/17919.png](https://cdn.luogu.com.cn/upload/pic/17919.png)
（从红色街区交费以后可以跳到周围的任意蓝色街区。）

现在的问题很简单。有三个飞飞侠，分别叫做 $X, Y, Z$。现在它们决定聚在一起玩，于是想往其中一人的位置集合。告诉你 $3$ 个飞飞侠的坐标，求往哪里集合大家需要花的费用总和最低。（费用相同时优先 $X$，次优先 $Y$）

inputFormat:
输入的第一行包含两个整数 $N$ 和 $M$，分别表示行数和列数。

接下来是 $2$ 个 $N\times M$ 的自然数矩阵，为 $B_{i,j}$ 和 $A_{i,j}$。

最后一行六个数，分别代表 $X, Y, Z$ 所在地的行号和列号。

outputFormat:
第一行输出一个字符 $X, Y$ 或者 $Z$。表示最优集合地点。

第二行输出一个整数，表示最小费用。

如果无法集合，只输出一行 `NO`。


title: 王者之剑

description:
![https://cdn.luogu.com.cn/upload/pic/17920.png](https://cdn.luogu.com.cn/upload/pic/17920.png)

这是在阿尔托利亚·潘德拉贡成为英灵前的事情，她正要去拔出石中剑成为亚瑟王，在这之前她要去收集一些宝石。

宝石排列在一个 $n \times m$ 的网格中，每个网格中有一块价值为 $v_{i,j}$ 的宝石，阿尔托利亚·潘德拉贡可以选择自己的起点。

开始时刻为 $0$ 秒。以下操作，每秒按顺序执行。

1. 在第 $i$ 秒开始的时候，阿尔托利亚·潘德拉贡在方格 $(x,y)$ 上，她可以拿走 $(x, y)$ 中的宝石。
2. 在偶数秒，阿尔托利亚·潘德拉贡周围四格的宝石会消失。
3. 若阿尔托利亚·潘德拉贡第 $i$ 秒开始时在方格 $(x,y)$ 上，则在第 $i+1$ 秒可以立即移动到 $(x+1,y),(x,y+1),(x-1,y)$ 或 $(x, y- 1)$ 上，也可以停留在（$x,y)$ 上。

求阿尔托利亚·潘德拉贡最多可以获得多少价值的宝石

inputFormat: 第一行给出数字 $N,M$ 代表行列数 $N,M$ 均小于等于 $100$，宝石的价值不会超过 $10000$。下面 $N$ 行 $M$ 列用于描述数字矩阵。

outputFormat: 输出最多可以拿到多少价值宝石。

hint: 姚金宇的原创题。


title: 「生物」能量流动

description:
生物课上，小 F 学习到了食物链、食物网的相关内容。

他学到，能量是逐级递减的。比如在食物链上，两个链接起来的生物 $A \rightarrow B$（意思是 $B$ 吃 $A$）之间的能量传递效率最多只有 $\frac 1 5$；而研究种间关系，能够使能量流向对人类最有益的部分。

现在，小 F 想研究一下能量流动的关系，于是他在脑海里创造了一个生态的系统。

在这个生态的系统里，有 $n+2$ 种生物，其中 $0$ 是生产者，整个生态系统所流经的能量由它固定；你是贪婪的顶级掠食者 $n + 1$，可以捕食所有生物；其他的掠食者 $[1, n]$ 各有各的喜好，只会捕食编号在 $[0, r_i]$ 的生物。由于天然形成的强弱顺序，上述关系满足 $r_i \leq r_{i + 1}(1 \leq i < n),$ $r_i < i(1 \leq i \leq n)$。

每种动物需要摄取至少 $a_i$ 单位能量才能存活；一个生物摄取到的能量可以传递给捕食者，但传递效率都不超过 $\frac 1 5$。也就是说，假设该动物捕获了 $b_i$ 单位的能量，所有捕食它的掠食者得到的能量总和 $c_i$，那么有：
* $b_i \geq a_i$
* $c_i \leq \frac 1 5 b_i$

你希望知道，在所有生物都存活的情况下，在最优情况下你能获取到的最大能量是多少。

inputFormat:
输入第一行两个整数 $n, a_0(1 \leq n \leq 10 ^ 5, 1 \leq a_0 \leq 10 ^ 9)$。$a_0$ 是生产者固定的能量值。

接下来 $n$ 行，每行 $2$ 个正整数，表示 $a_i, r_i(1 \leq a_i \leq 10 ^ 9)$。

数据保证，$0\leq r_i < i, r_i \leq r_{i + 1}$。

outputFormat:
输出一行一个浮点数，表示你——顶级掠食者——能得到的最大能量。如果不能使得所有生物存活（包括你自己），请输出 $-1$。

你的答案与参考答案的相对误差或者绝对误差不超过 $10 ^ {-8}$ 即被认为是正确的。如果你的程序是正确的，可以不用考虑精度问题。

hint:
### 样例 1 解释

最优情况下：
* 1 号掠食者捕食生产者 0，捕食 5 点能量，传递效率为 $\frac 1 5$，得到 1 点能量。
* 2 号掠食者捕食生产者 0，捕食 4 点能量，传递效率为 $\frac 1 5$，得到 0.8 点能量。
* 2 号掠食者捕食掠食者 1，捕食 1 点能量，传递效率为 $\frac 1 5$，得到 0.2 点能量。

可怜的你只能捕获 2 号掠食者的能量，捕食 1 点能量，得到 0.2 点能量。

### 样例 2, 3 解释

由于 2 号掠食者开始减肥不吃肉了（也有可能是打不过 1 了），所以所需的生产者能量从 9 点变成了 10 点。

### 子任务

子任务 $1(21 \mathrm{pts}) : n \leq 100$；

子任务 $2(89 \mathrm{pts}) : n \leq 10 ^ 5$。


title: 「数学」约数个数和

description:
小 F 在数学课上与同学闲聊。

> 给你一个正整数，计算他的约数个数。

「你们竞赛就学这个啊？太简单了吧。」

「……」

> 给你一个正整数，计算他的所有约数的约数个数和。

「我想想……嗯，还是不难的。诶，你们竞赛还能报名吗？」

「……」

> 给你一个正整数，计算他的所有约数的所有约数的约数个数和。

「哎呀反正你们电脑总是能爆算出来的嘛，快给我说在哪报名。」

「……」

> 给你一个正整数，计算他的所有约数的所有约数的所有约数的约数个数和。

「有完没完了？」

「……」

被嘲讽的小 F 将这个问题交给了你，请展示你的爆算实力。

给你一个正整数 $N$，请计算 $N$ 的 $($所有约数的$)\times K$ 约数个数和。

答案可能很大，请输出对 $998244353$ 取模的结果。

outputFormat: 输出一行一个非负整数，表示所求的答案对 $998244353$ 取模的结果。


title: [Ynoi2011] 遥远的过去

background:
小学六年级的时候学了JAVA，写了个小游戏，大概是把我奥数老师的头弹飞出去拿来打青蛙的，看来我小时候就懂膜蛤和P头了。

现在感觉当时很多东西没理解，都在乱写，程序里面全是if，就这样还是写出来了，还拿了个科创大赛一等奖（可以加5分中考分的，可不算很野鸡！）

所以一直感觉我其实是很喜欢做一些有创造性的东西的，这点之后也会体现出来。

上了初中，因为之前学过点小学奥数，同时也有学一些数学竞赛的东西，所以感觉老师讲课都很平凡，没什么兴趣。

第一次接触到了信息学竞赛，当时感觉还是挺有趣的，不过也没怎么认真学。

学校里面有OI的培训，但由于学校里面在教Pascal，我当时已经学过JAVA了，自然觉得这个语言很落后，垃圾，所以也没怎么听课，印象中我去参加个选拔考试，有个鸡兔同笼的题，我写了个解方程被扣分了，老师给的正解是 while( a-- ) b++ 这样的东西，然后就决定不去了。

初二考了一次NOIP普及组，当时只拿了120，第二题是个表达式求值，我写了很久很久都一直挂，然后就凉凉了。

考完之后得知班上几个同学考了全省前10，感觉他们好强，当时还是很有好胜心的，于是决定好好学OI，初三打爆他们。

初三的时候考了295，被两个当时初二的小朋友打爆了，不过我是初三里面最高分（

那两个小朋友好像现在都去茶园了，果然是神仙。

感觉初中还是挺好玩的，虽然天天和毒瘤老师斗智斗勇，但还是很有趣。

【记得配图，内容：写的小游戏的截图，还有noip的成绩】

由于这是Ynoi，不是出题人拿来写奇怪的文字的地方，所以你需要做一个数据结构题：

description:
小 F 决定设计出一种字符集超大的语言——Z 语言，哪怕有时额外的字符并没有什么用。

这种语言的特点是：

* 字符集非常大，甚至可能有 $2147483648(2 ^ {31})$ 种字符；

* 每个单词由一系列**两两不同**的字符组成；

* 字符既能比较相同和不同，也能比较大小，因此之后我们用数字来表示 Z 语言中稀奇古怪的字符；

* 两个看起来完全不同的单词也可能是同一个单词，因为：只要两个单词中第 K 大的字符所在的位置相同，那么其实就是本质上相同的单词。例如 $\{1, 2, 3, 4, 5\}$ 与 $\{2, 3, 23, 233, 23333\}$ 是相同的。（所以你可以用 Z 语言很方便地加密信息！）

现在，小 F 打算将 Z 语言应用到实际中。比如，他点开了一道电脑里的算法题：

> 给定两个字符串 $A, B$ ，求 $B$ 作为子串在 $A$ 中被匹配的次数。

 小 F 当然知道这是一个可以用 KMP 解决的基础题。但是，他在用 Z 语言的匹配实现 Z-KMP 的时候遇到了问题，你能帮帮他吗？

为了验证你是不是真的明白小 F 在说什么，小 F 会修改 $B$ 串很多次来问你。可不准偷懒哦！

你的程序需要支持的操作详见输入输出格式。

inputFormat:
输入第一行两个整数 $n, m, q(1 \leq n, m, q \leq 10 ^ 5)$，表示 $A, B$ 串的长度以及操作次数。

第二行 $n$ 个非负整数，第 $i$ 个表示 $A$ 串的第 $i$ 个字符 $A_i$ $(0 \leq A_i \leq 2147483647=2 ^ {31} - 1)$。

第三行 $m$ 个非负整数，第 $i$ 个表示 $B$ 串的第 $i$ 个字符 $B_i$ $(0 \leq B_i \leq 2147483647=2 ^ {31} - 1)$。

接下来 $q$ 行，每行两个正整数 $x_i, c_i$ $(1 \leq c_i \leq 2147483647=2 ^ {31} - 1)$，表示将 $B$ 串 $x_i$ 位置上的字符由 $B_{x_i}$ 改为 $c_i$。

数据保证，任意时刻 $A$ 和 $B$ 均是满足前述要求的合法 Z 字符串。

outputFormat: **在每次修改完成后**，请输出 $B$ 作为子串在 $A$ 中被 Z-匹配 的次数。

hint:
Idea：nzhtl1477，Solution：nzhtl1477，Code：nzhtl1477，Data：nzhtl1477( partially uploaded )

### 样例 1 解释

在第一次修改后，$\{3, 5, 1\}$ 并不能被任何一个 $A$ 中的子串匹配上。

在第二次修改后，$\{6, 5, 1\}$ 能被 $A$ 中所有长度为 $3$ 的串匹配上，原因是 A 是单调减的，而 B 也是单调减的，因此 $A$ 中所有长度为 $3$ 的串与 $B$ 排名相同的处于相同位置。

### 子任务

子任务 $1(31 \mathrm{pts}) : n, m \leq 100, q \leq 1000$；

子任务 $2(41 \mathrm{pts}) : n, m \leq 1000, q \leq 5 \times 10 ^ 4$；

子任务 $3(78 \mathrm{pts}) : n, m, q \leq 10 ^ 5$。


title: 「语文」凑字数

background: 数据的锅修好了！

description:
时间在一秒一秒地减少着，然而小 F 仍对着作文题冥思苦想。看起来，他又写不完作文了。

然而，小 F 有一种特殊的凑字数技巧——不停换行。这是因为，作文纸每行 $L$ 个字，而最低字数限制是以行数来计算的。

也就是说，只要写到了 $M$ 行（不含标题）即认为时满足要求，写到意味着这一行上有字。注意，由于作文格式要求，每段首行会**有两个字符的缩进空格**。

现在，他已经构思好了 $N$ 句话，每句话有着自己的长度 $a_i$ ——包括标点符号，不考虑因句号等在最后一格之外而不换行的情况。这几句话的关联或强或弱，关联强的更适合放在一段，关联弱的更适合分段，然而因为凑字数小 F 可以对任意两句话之间进行换行以分段。

关联关系会用一种特殊的方式来表示。我们知道，作文改卷时会将作文的得分点划分为几个主要部分，比如全国卷分为基础，表达，发展三个部分；每个部分拥有着相同的总分，比如对于全国卷来说是 $20$ 分；每个部分的最低均为 $0$ 分，也就是说哪怕扣到 $0$ 以下也算 $0$ 分。在这里，我们的评分标准有 $K$ 个部分，每个部分有 $S$ 分的满分。根据方面的不同，小 F 将两句话的关联关系用一个 $K$ 元组 $s_i = (s_{i,1}, s_{i, 2}, \cdots, s_{i, K})$ 表示，其中每个数都是整数，第 $j$ 个数 $s_{i, j}$ 表示：
* 如果是正数，那么表示拆开 $i, i + 1$ 这两句话会导致第 $j$ 部分得分扣 $s_{i, j}$ 分 。
* 如果是负数，那么表示**不**拆开这两句话第 $j$ 部分得分扣 $-s_{i, j}$ 分。
* 如果为 0，那么表示是否拆开这两句话对得分没有影响。

从满分开始，在计算完上面的扣分之后可以得到一个初步的总分。在这之后，最低字数线上每空一行，会扣 $C$ 分字数分，总分扣至 0 为止。

如果能够拿到高分作文，小 F 就可以得到老师的大拇指！所以，请你帮小 F 设计出一种方案以最大化得分。

inputFormat:
输入第一行为 $6$ 个整数，$N, M, L, K, S, C$，对应题目描述里的内容。

输入第二行为 $N$ 个整数，第 $i$ 个为 $a_i$，即每句话的长度。

接下来 $N - 1$ 行，每行 $K$ 个整数，第 $i$ 行第 $j$ 个表示 $s_{i, j}$。

outputFormat: 输出一行一个非负整数，表示你所求得的最大得分。

hint:
### 样例 1 解释

这是样例 1 不分段的情况：

![](https://cdn.luogu.com.cn/upload/pic/21276.png )

这样做，得分是 $10 + 9 - 5 = 14$ 分。

我们发现，字数分太痛了，于是我们一定要去避免它。

最优解如下：

![](https://cdn.luogu.com.cn/upload/pic/21277.png)

这样做，得分是 $8 + 10 - 0 = 18$ 分。

### 样例 2 解释

即使换行可以避免一分字数扣分，但是相应地会扣掉两分，所以不如不换。

### 子任务

子任务 $1(21 \mathrm{pts}) : N \leq 10$；

子任务 $2(21 \mathrm{pts}) : K = 1$；

子任务 $3(31 \mathrm{pts}) : N \times a_i \leq 800$；

子任务 $4(77 \mathrm{pts}) :$
* $1 \leq N, M, a_i \leq 200$
* $3 \leq L \leq 200$
* $1 \leq K \leq 5$
* $0 \leq S, C, |s_{i, j}| \leq 200$


title: [BJWC2018] 数字统计

description:
小A 正在研究一些数字统计问题。有一天他突然看到了一个这样的问题：

将[L..R]中的所有整数用M 位二进制数表示（允许出现前导0）。现在将这些数中的每一个作如下变换：

从这个数的最低两位开始，如果这两位都是0，那么X=1，否则X=0。现在将这两位删去，然后将X 放在原来最低位的位置上。重复这个变换直到这个数只剩下一位为止。

例如01001 的变换过程如下：

01001-->0100-->011-->00-->1。

现在的问题是变换后的所有数中，值为Y（Y 为0 或1）的有多少个？

小A 不会了，他想让你帮助他完成这个问题。

inputFormat:
输入文件包含多组测试数据。

第一行，一个整数T，表示测试数据的组数。

接下来的T 节，每节对应一组测试数据，格式如下：

第一行，两个整数M、Y。

第二行，两个M 位二进制数L、R。

outputFormat: 对于每组测试数据，输出一行，一个二进制数，表示该组测试数据中[L..R]中的所有整数变换后的值为Y 的个数。这里的二进制数不允许出现前导0。

hint:
对于20%的数据：1 ≤ M ≤ 16。

对于40%的数据：1 ≤ M ≤ 32。

对于100%的数据：1 ≤ M ≤ 200，1 ≤ T ≤ 50。


title: [BJWC2018] 基础匹配算法练习题

description:
小 S 最近学会了二分图匈牙利匹配算法。

现在二分图的 X 部有 $N$ 个数字 $A_i$，Y 部有 $K$ 个数字 $C_i$。

已知如果 $A_i + C_j \le  Z$，那么 $A_i$ 和 $C_j$ 之间就有一条边，求二分图（X，E，Y）的最大匹配数。

小 S 是初学者，所以她想做多做一些练习来巩固知识。于是她找到了一个长度为 $M$ 的正整数数组 $B$，每次她会在 $B$ 数组中抽取一段连续的区间 $[L_i,R_i]$，把区间 $[L_i,R_i]$ 的所有数字作为二分图 Y 部的 $K$ 个数字 $C_i$，然后重新求一次二分图最大匹配数。

小 S 打算一共做 $Q$ 次练习，但是她不知道每次计算出的答案对不对，你能帮帮她吗？

inputFormat:
第一行为三个正整数 $N,M,Z$。

第二行为 $N$ 个正整数，第 $i$ 个正整数表示 $A_i$。

第三行为 $M$ 个正整数，第 $i$ 个正整数表示 $B_i$。

第四行为一个整数 $Q$ 表示询问个数。

接下来 $Q$ 行每行两个正整数，第 $i$ 行的两个正整数分别表示 $L_i,R_i$。

outputFormat: 对于每次练习，输出该次练习的答案。


title: [BJWC2018] 上学路线

description:
小 B 所在的城市的道路构成了一个方形网格，它的西南角为 $(0,0)$，东北角为 $(N,M)$。

小 B 家住在西南角，学校在东北角。现在有 $T$ 个路口进行施工，小 B 不能通过这些路口。小 B 喜欢走最短的路径到达目的地，因此他每天上学时都只会向东或北行走；而小 B 又喜欢走不同的路径，因此他问你按照他走最短路径的规则，他可以选择的不同的上学路线有多少条。由于答案可能很大，所以小 B 只需要让你求出路径数 mod $P$ 的值。

inputFormat:
第一行为四个整数 $N$ 、 $M$ 、 $T$ 、 $P$。

接下来的 $T$ 行，每行两个整数，表示施工的路口的坐标。

outputFormat: 一行一个整数，表示路径数 mod $P$ 的值。


title: [BJWC2018] 第k大斜率

description:
在平面直角坐标系上，有 $n$ 个不同的点。任意两个不同的点确定了一条直线。请求出所有斜率存在的直线按斜率从大到小排序后，第 $k$ 条直线的斜率为多少。

为了避免精度误差，请输出斜率向下取整后的结果。（例如：$\lfloor 1.5 \rfloor = 1$，$\lfloor -1.5 \rfloor = -2$）。

inputFormat:
第一行，包含两个正整数 $n$ 和 $k$。
接下来 $n$ 行，每行包含两个整数 $x_i, y_i$，表示每个点的横纵坐标。

outputFormat: 输出一行，包含一个整数，表示第 $k$ 大的斜率向下取整的结果。


title: [BJWC2018] 餐巾计划问题

background: **本题和网络流24题中的餐巾计划不为重题**

description:
一个餐厅在相继的 $n$ 天里，每天需用的餐巾数不尽相同。假设第 $i$ 天 $(i=1, 2, ..., n)$ 需要 $r_i$ 块餐巾。餐厅可以在任意时刻购买新的餐巾，每块餐巾的费用为 $p$ 。使用过的旧餐巾，则需要经过清洗才能重新使用。把一块旧餐巾送到清洗店A，需要等待 $m_1$ 天后才能拿到新餐巾，其费用为 $c_1$ ；把一块旧餐巾送到清洗店B，需要等待 $m_2$ 天后才能拿到新餐巾，其费用为 $c_2$ 。例如，将一块第 $k$ 天使用过的餐巾送到清洗店A清洗，则可以在第 $k+m_1$ 天使用。

请为餐厅合理地安排好 $n$ 天中餐巾使用计划，使总的花费最小。

inputFormat:
第一行，包含六个个正整数  $n, m_1, m_2, c_1, c_2, p$ 。

接下来输入 $n$ 行，每行包含一个正整数 $r_i$ 。

outputFormat: 输出一行，包含一个正整数，表示最小的总花费。

hint:
**【样例说明】**

第 1 天：买8块餐巾，花费24。送2块餐巾去清洗店A，6块餐巾去清洗店B。

第 2 天：取回2块清洗店A的餐巾，花费4。送1块餐巾去清洗店B。

第 3 天：取回6块清洗店B的餐巾，花费6。

第 4 天：取回1块清洗店B的餐巾，花费1。这样就用了最少的钱。

**【数据规模和约定】**

对于30%的数据，$1 \leq n \leq 5$ ，$1 \leq c_1, c_2, p \leq 5$ ， $1 \leq r_i \leq 5$ 。

对于50%的数据，$1 \leq n \leq 100$ ，$1 \leq r_i \leq 50$ 。

对于70%的数据，$1 \leq n \leq 5000$ 。

对于100%的数据，$1 \leq n \leq 200000$ ， $1 \leq m_1, m_2 \leq n$ ， $1 \leq c_1, c_2, p \leq 100$ ， $1 \leq r_i \leq 100$ 。


title: [BJWC2018] 序列合并

background: 绿意盎然的一天，Scape去XX赛区加冕为王。

description:
Scape倒开题目，看到了这样一道题：

有一个序列 A 和 L,R ，每次可以合并相邻的 K 个元素（要求 L<=K<=R ），代价为这 K 个元素的和并合并产生一个新元素，权值为这 K 个元素的和。

求把整个序列合并为一个元素的最小代价。

T 组数据， T<=10, n<=300 。

Scape 想都不想就写了一个 $n^4$ 暴力，结果居然 T 了，作为 XX 之王的 Scape 自然不会管这种辣鸡题，请你写出这道题。

inputFormat:
第一行一个整数 T(T<=10) ，表示数据组数。

每组数据第一行三个整数 n,L,R 表示序列 A 的长度，和 K 的上下界限制。

第二行 n 个整数表示序列 A 。

outputFormat: 每行一个整数表示结果，无解输出 0。

hint:
对于 20% 的数据， $n≤20$ 。

对于 60% 的数据， $n≤50$ 。

对于 100% 的数据， $n≤300,A_i≤100$ 。


title: [BJWC2018] Border 的四种求法

background: Scape 一到机房，所有做题的人便都看着他笑，有的叫道，“Scape，你一定又被标准分倍杀了！”他不回答，对柜里说，“测两个程序，看一眼成绩单。”便拷出两个程序。他们又故意的高声嚷道，“你怎么欧拉回路和逆序对都WA了！”……

description:
Scape 知道，以上的故事只是 OI 生涯里的一个意外，为了证明自己，他决定教你 $\text{Border}$ 的四种求法。

给一个小写字母字符串 $S$，$q$ 次询问每次给出 $l,r$ ，求 $s_{l\ldots r}$ 的 $\text{Border}$。

$\text{Border}$：对于给定的串 $s$，最大的 $i$ 使得 $s_{1\ldots i} = s_{|s|-i+1\ldots |s|}$。$|s|$ 为 $s$ 的长度。

inputFormat:
第一行一个字符串 $S$。

第二行一个整数 $q$ 表示询问个数。

接下来的 $q$ 行每行两个整数 $l,r$ 表示一个询问。

outputFormat: 对于每组询问输出答案。

hint:
对于 $30%$ 的数据， $n,q\leq 1000$ 。

对于 $50%$ 的数据， $n,q\leq 2\times 10^4$ 。

对于另外 $30\%$ 的数据，答案至少为 $r-l+1$ 的一半。

对于 $100\%$ 的数据， $n,q\leq 2\times 10^5$ 。


title: [BJWC2018] 神奇的钟点

description:
一天，小 L 看到了 3 块钟表，分别显示着 $\texttt{01:08}$、$\texttt{03:40}$、$\texttt{13:52}$。小 L 发现，每块表上的时间都是 $\texttt{hh:mm}$ 的形式，其中 $\texttt{hh}$ 表示小时，$\texttt{mm}$ 表示分钟，而且都不是整点（即 $0\leqslant\texttt{hh}<24$，$1\leqslant\texttt{mm}<60$）。

回想起小学数学老师刚刚讲的关于比例的知识，$\texttt{hh:mm}$ 也表示一个比，它的值等于 $\frac{\texttt{hh}}{\texttt{mm}}$。这时小 L 发现了一件神奇的事情：把这三个钟点加起来会得到 $\texttt{18:40}$，这也是一个不是整点的合法时间（注意小时数要小于 $24$），它对应的比值 $\frac{9}{20}$，与这三个钟点对应的比值 $\frac{1}{8}$、$\frac{3}{40}$、$\frac{1}{4}$ 之和竟然相等！

现在小 L 想知道，把所有的满足这个神奇的性质的 3 个钟点组成的钟点组按照字典序排序后，第 $k$ 小的是什么。

inputFormat: 输入仅包含一个正整数 $k$。

outputFormat: 输出字典序第 $k$ 小的满足题目所述神奇性质的钟点组，以一个空格隔开，详见样例输出。如果答案不存在，输出 `-1`。

hint:
**【样例说明】**

注意钟点可以相同。

**【数据规模和约定】**

对于 $30\%$ 的数据，$k\leqslant 1000$。
对于 $60\%$ 的数据，$k\leqslant 20000$。
对于 $100\%$ 的数据，$1\leqslant k\leqslant 2\times 10^9$。


title: [BJWC2018] 最长上升子序列

description:
现在有一个长度为 $n$ 的随机排列，求它的最长上升子序列长度的期望。

为了避免精度误差，你只需要输出答案模 $998244353$ 的余数。

inputFormat: 输入只包含一个正整数 $n$。

outputFormat:
输出只包含一个非负整数，表示答案模 $998244353$ 的余数。

可以证明，答案一定为有理数，设其为 $a/b$（$a, b$ 为互质的整数），你输出的整数为 $x$，则你需要保证 $0 \le x < 998244353$ 且 $a$ 与 $b x$ 模 $998244353$ 同余。

hint:
**【样例 \#2 说明】**

这是 $3/2$。

**【数据规模和约定】**

对于 $100 \%$ 的数据，$1 \le n \le 28$。

共有 25 组数据，对于第 $i$ 组数据（$1 \le i \le 25$），$n = i + 3$。


title: [BJWC2018] 拓扑序列

description:
小 C 最近学习了拓扑排序的相关知识。对一个有向无环图 $G$ 进行拓扑排序，是将 $G$ 中所有顶点排成一个线性序列，使得对图 $G$ 中任意一条有向边 $(u,v)$，$u$ 在线性序列中出现在 $v$ 之前。例如，如果图 $G$ 的点集为 $\{1,2,3,4\}$，边集为 $\{(1,2)
,(1,3),(2,4),(3,4)\}$，那么 $(1,2,3,4)$ 和 $(1,3,2,4)$ 都是图 $G$ 的拓扑序列。

现在小 C 对一个简单（无重边）有向无环图进行了拓扑排序，但不小心把原图弄丢了。除了拓扑序列，小 C 只记得原图的边数为 $k$，而且图中存在一个顶点 $u$ 可以到达其他所有顶点。他想知道有多少个满足上述要求的简单有向无环图。由于答案可能很大，你只需要输出答案模 $m$ 的余数。

inputFormat:
输入第一行包含三个整数 $n,k,m$。

第二行是空格隔开的 $n$ 个正整数 $a_1,a_2,…,a_n$，表示原图的一个拓扑序列，保证是 $1$ 到 $n$ 的一个排列。

outputFormat: 仅输出一个整数， 表示满足要求的简单有向无环图个数模 $m$ 的余数。


title: [BJWC2018] Kakuro

background:
首先介绍一下Kakuro(カックロ) 这个游戏。

游戏规则为：

• 方形空格中填入1 ~ 9 的整数。

• 被斜线分开的方格中，右上角的数字等于其右侧邻接之连续方格中数字之和，左下角的数字等于其下方邻接之连续方格中数字之和。

• 无论是横向还是纵向，连续方格中的数字不能重复。

![](https://cdn.luogu.com.cn/upload/pic/17946.png)
![](https://cdn.luogu.com.cn/upload/pic/17947.png)

左边为一个Kakuro 游戏，右边为这个游戏的唯一解。

我们称一开始给出的数字为线索，称需要填入数字的地方为空格。如果一个格子包含线索那么就不需要填入数字。我们约定所有的谜题都非空，即至少有一个空格需要被填入。

**注意：在以下题目中的游戏规则可能会有所不同，请认真阅读在每个
题目下的规则。**

description:
游戏规则：

• 空格中填入正整数。

• 被斜线分开的方格中，右上角的数字等于其右侧邻接之连续方格中数字之和，左下角的数字等于其下方邻接之连续方格中数字之和。

Apia 给了Rimbaud 一个Kakuro 谜题。心不灵手不巧的Rimbaud 根本不会做Kakuro，所以只在空格里面填上了一些随机的数字，称这个为一个局面，即包含了谜题一开始给出的线索和后面填入的数字。

现在Rimbaud 希望能修改这个局面使得她的答案是一个合法解。这个局面中有些数字(**包括一开始的给出线索和后面填入的数字**) 是可以修改的。每个数字都有个特定的代价，将这个数字加1 或者减1 都得付出这个数字对应的代价。注意对于一组合法解，必须满足游戏规则，也就是**空格中填的数字必须是正整数并且满足和的条件，但是不要求不重复**。

Rimbaud 希望用最少的代价让这个局面变得合法，如果不可能那么输出-1。

inputFormat:
第一行，两个正整数表示n,m 表示这个游戏的行和列。

接下来n 行，每行包含m 个0 到4 的数字，第i 行第j 列表示第i 行第j 列格子的种类。

• 0 表示这个格子既不是空格也不是线索。

• 1 表示这个格子左下角包含线索，右上角没有线索。

• 2 表示这个格子右上角包含线索，左下角没有线索。

• 3 表示这个格子左下角右上角都包含线索。

• 4 表示这个格子为空格。

输入保证这个从格式上来说一定是个合法的Kakuro 谜题，即每一段连续的空格的左边或者上面的格子包含线索。

接下来n 行，每行包含若干个正整数，按从左往右的顺序给出初始局面中的每个数字。特别地如果这个格子的种类为3，那么先给出左下角的线索，再给出右上角的线索。

接下来n 行，每行包含若干个整数，按从左往右的顺序给出初始局面中的每个数字对应的代价。如果代价为-1 表示这个格子不能修改，否则代价为非负整数。注意3 号格子的两个线索有着两个不同的代价。

**样例1 给出了上面的谜题的输入，请在做题前阅读样例1 确保你理解了输入格式。**

outputFormat: 一个整数表示最小的代价，如果不可能输出-1。

hint:
对于5% 的数据，保证所有的代价都为-1。

对于20% 的数据，保证所有空格中的数字代价都为-1。

对于另外30% 的数据，保证所有代表线索的数字的代价都为-1。

对于另外20% 的数据，保证只有第一行第一列包含线索，剩下的地方全都是空格。

对于100% 的数据，保证3 ≤ n,m ≤ 30，保证初始局面中的每个数字不超过$10^6$，保证每个数字的代价不超过$10^6$。


title: [BJWC2018] Cross sum

background:
首先介绍一下Kakuro(カックロ) 这个游戏。

游戏规则为：

- 方形空格中填入 $1\sim 9$ 的整数。
- 被斜线分开的方格中，右上角的数字等于其右侧邻接之连续方格中数字之和，左下角的数字等于其下方邻接之连续方格中数字之和。
- 无论是横向还是纵向，连续方格中的数字不能重复。

![](https://cdn.luogu.com.cn/upload/pic/17946.png)
![](https://cdn.luogu.com.cn/upload/pic/17947.png)

左边为一个Kakuro 游戏，右边为这个游戏的唯一解。

我们称一开始给出的数字为线索，称需要填入数字的地方为空格。如果一个格子包含线索那么就不需要填入数字。我们约定所有的谜题都非空，即至少有一个空格需要被填入。

**注意：在以下题目中的游戏规则可能会有所不同，请认真阅读在每个
题目下的规则。**

description:
游戏规则：

- 空格中填入正整数。
- 被斜线分开的方格中，右上角的数字等于其右侧邻接之连续方格中数字之异或和，左下角的数字等于其下方邻接之连续方格中数字之异或和。
- 所有空格中填入的整数都不能重复。

Apia 给了 Rimbaud 一个 Kakuro 谜题。心不灵手不巧的 Rimbaud 根本不会做 Kakuro，所以她请求你帮她解决。由于 Rimbaud 很年幼，只会对不超过 $2^{60}-1$ 的数字进行运算。所以希望谜题的解中每个数字都不超过
 $2^{60}-1$。

inputFormat:
每组数据包含多组测试数据。第一行包含一个整数 $T$ 表示测试数据组数。

对于每组测试数据，第一行，两个正整数 $n,m$ 表示这个游戏的行和列。

接下来 $n$ 行，每行包含 $m$ 个 $0$ 到 $4$ 的数字，第 $i$ 行第 $j$ 列表示第 $i$ 行第 $j$ 列格子的种类。

- $0$ 表示这个格子既不是空格也不是线索。
- $1$ 表示这个格子左下角包含线索，右上角没有线索。
- $2$ 表示这个格子右上角包含线索，左下角没有线索。
- $3$ 表示这个格子左下角右上角都包含线索。
- $4$ 表示这个格子为空格。

输入保证这个从格式上来说一定是个合法的 Kakuro 谜题，即每一段连续的空格的左边或者上面的格子包含线索。

接下来 $n$ 行，每行包含若干个**非负整数**，按从左往右的顺序给出谜题中的每个线索。特别地如果这个格子的种类为 $3$，那么先给出左下角的线索，再给出右上角的线索。

outputFormat: 对于每组测试数据，如果有解，那么输出 $n$ 行，每行按从左往右的顺序输出往空格中填入的数，要求空格内填入的数字在 $1$ 到 $2^{60}-1$ 之间。否则输出一个 $-1$。

hint:
对于 $10\%$ 的数据，保证 $n,m \leq 3$。

对于 $30\%$ 的数据，保证$n,m \leq 15$。

对于 $50\%$ 的数据，保证$n,m \leq 40$。

对于另外 $20\%$ 的数据，保证只有第一行第一列包含线索，剩下的地方全都是空格。

对于 $100\%$ 的数据，保证$3 \leq n,m \leq 200$，$1\leq T \leq 5$，保证初始局面中的每个数字不超过 $2^{60}-1$。


title: [BJWC2018] Kreuzsummen

description:
游戏规则：

• 方形空格中填入1 ~ k 的整数。

• 被斜线分开的方格中，右上角的数字等于其右侧邻接之连续方格中数字之和，左下角的数字等于其下方邻接之连续方格中数字之和。

• 无论是横向还是纵向，连续方格中的数字不能重复。

Apia 给了Rimbaud 一个Kakuro 谜题。心不灵手不巧的Rimbaud 发现自己总是做不出Kakuro。她怀疑原因是Apia 给的题目难度太高而不是自己太菜。所以她想评价一下这个题目的难度。

Rimbaud 认为一个Kakuro 谜题的难度为每个空格的候选数个数的和。我们来定义一下对于每个空格的候选数，这里的候选数为只考虑这个格子在初始谜题下对应的行和列线索和数字不能重复的条件下可以填的数字集合。

如果某连续4 个空格对应的线索为10，那么这四个数只可能是1 + 2 + 3 + 4，也就是这几个空格在这个线索的限制下候选数集合为{1, 2, 3, 4}。

更一般的，如果某连续c 个空格对应的线索为s，那么考虑所有数值1 ~ k 之间，不重复并且和为s 的c 元组，这几个空格在这个线索限制下的候选数集合为出现在这些c 元组中的所有数字。对于每个空格，它的候选数集合为行限制下的候选数和列限制下的候选数的交。

![](https://cdn.luogu.com.cn/upload/pic/17946.png)

在这个谜题中，我们考虑第2 行第2 列的空格。这个空格的行线索为16，对应的候选数集合为{7, 9}。这个空格的列线索为23，对应的候选数{6, 8, 9}，所以这个空格的候选数集合为{9}。第2 行第3 列的空格的行线索对应的候选数集合为{7, 9}，列线索的I 应的候选数集合为{6, 7, 8, 9}，所以这个空格的候选数集合为{7, 9}。注意虽然我们可以通过先确定第2 行第2 列的数字，然后根据行线索推算出第2 行第3 列的数字，但是Rimbaud **只会考虑初始的线索**。

请帮助Rimbaud 求出这个谜题的难度即所有的空格的候选数个数的和。

inputFormat:
第一行，四个正整数表示n, m, k, T 表示这个游戏的行，列，数值范围和总线索个数。
接下来T 行，每行五个正整数，$t, x, y_1, y_2, s(t \in \{0, 1\}, y_1 ≤ y_2)$。其中t 表示这个线索的种类，如果t = 0，那么表示这个线索为行线索，第x 行第y1 列到y2 列之间的数字和为s。如果t = 1，那么表示这个线索为行线索，
第x 列第y1 行到y2 行之间的数字和为s。数据中的行和列都从1 开始标号。

这个谜题的空格为所有线索对应的空格的并集。输入保证这个从格式上来说一定是个合法的Kakuro 谜题，即每一段连续的空格的左边或者上面的格子包含线索，并且每个空格出现了恰好两次。

**数据中可能出现某些位置的候选数集合为空或者无解的情况**。对于这种情况还是只需要按定义求出这个谜题的难度即可。

outputFormat: 输出一个整数表示答案。


title: 巧克力王国

description:
巧克力王国里的巧克力都是由牛奶和可可做成的。但是并不是每一块巧克力都受王国人民的欢迎，因为大家都不喜欢过于甜的巧克力。

对于每一块巧克力，我们设 $x$ 和 $y$ 为其牛奶和可可的含量。由于每个人对于甜的程度都有自己的评判标准，所以每个人都有两个参数 $a$ 和 $b$ ，分别为他自己为牛奶和可可定义的权重， 因此牛奶和可可含量分别为 $x$ 和 $y$ 的巧克力对于他的甜味程度即为 $ax+by$。而每个人又有一个甜味限度 $c$ ，所有甜味程度大于等于 $c$ 的巧克力他都无法接受。每块巧克力都有一个美味值 $h$ 。

现在我们想知道对于每个人，他所能接受的巧克力的美味值之和为多少。

inputFormat:
第一行两个正整数 $n$ 和 $m$ ，分别表示巧克力个数和询问个数。
接下来$n$行，每行三个整数 $x , y , h$ ，含义如题目所示。
再接下来 $m$ 行，每行三个整数 $a , b , c$ ，含义如题目所示。

outputFormat: 输出$m$行，其中第$i$行表示第$i$个人所能接受的巧克力的美味值之和。


title: [CTSC2014] 企鹅 QQ

background: PenguinQQ 是中国最大、最具影响力的 SNS（Social Networking Services）网站，以实名制为基础，为用户提供日志、群、即时通讯、相册、集市等丰富强大的互联网功能体验，满足用户对社交、资讯、娱乐、交易等多方面的需求。

description:
小 Q 是 PenguinQQ 网站的管理员，他最近在进行一项有趣的研究——哪些账户是同一个人注册的。经过长时间的分析，小Q发现同一个人注册的账户名称总是很相似的，例如 Penguin1，Penguin2，Penguin3……于是小 Q 决定先对这种相似的情形进行统计。

小 Q 定义，若两个账户名称是相似的，当且仅当这两个字符串等长且恰好只有一位不同。例如“Penguin1”和“Penguin2”是相似的，但“Penguin1”和“2Penguin”不是相似的。而小 Q 想知道，在给定的 $n$ 个账户名称中，有多少对是相似的。

为了简化你的工作，小Q给你的N 个字符串长度均等于L ，且只包含大小写字母、数字、下划线以及‘@’共64种字符，而且不存在两个相同的账户名称。

inputFormat:
第一行包含三个正整数 $N,L,S$。其中 $N$ 表示账户名称数量，$L$ 表示账户名称长度，$S$ 用来表示字符集规模大小，它的值只可能为 $2$ 或 $64$。

若 $S$ 等于 $2$，账户名称中只包含字符 `0` 和 `1` 共 $2$ 种字符；

若 $S$ 等于 $64$，账户名称中可能包含大小写字母、数字、下划线以及 `@` 共 $64$ 种字符。

随后 $N$ 行，每行一个长度为 $L$ 的字符串，用来描述一个账户名称。数据保证 $N$ 个字符串是两两不同的。

outputFormat: 仅一行一个正整数，表示共有多少对相似的账户名称。


title: [CTSC2014] 插线板

background: #警告：滥用本题评测将封号

description:
Allison有非常多的电子设备，比如iMac,iPod,iPhone和iPad。所以她准备购买插线板来给电子设备充电。在做了大量的网络调研后，Allison发现了一款美丽精巧的天翼牌排插（如左下图所示）。在见到这个插线板的第一眼，Allison就被它的精美造型所吸引，于是她一次性购买了n个这种型号的插线板。

可是问题也随之而来，Allison的家中只有一个插座，她需要通过插线板的连接将电一层一层地导出（如右上图所示）。

插线板的连接方式是树形结构的：每个插线板的插头插在另一个插线板的插空中（除了根节点），插线板的连接不允许构成环。

每个插线板有火线，零线，地线三根导线，随着插线板数量的增加、导线的磨损，电路中导线与导线之间接触产生的电阻已经到了不能被忽视的地步。

如何来描述插线板的树形结构以及导线之间的电阻关系呢？Allison思考出来一个数学模型：用$a_i$代表第$i$个插线板的编号，$f_i$代表第$i$个插线板的插头所差的插线板（即$a_i$在树中的父亲），$1$代表火线，$2$代表零线，$3$代表地线，则整个网络的电阻可以用$R(a_i,f_i,x,y)(x,y∈\{1,2,3\})$来描述，它代表$a_i$的$x$线与$f_i$的$y$线之间的电阻值（在这个数学模型中，Allison认为火线和零线也是可能连接并且产生电阻的）下面是一个例子：

![](https://cdn.luogu.com.cn/upload/pic/17985.png)

由于时间的推移，导线与导线之间的电阻还可能发生变化。现在，Allison想知道在插线板树形电路中，当前时刻$a_i$插线板的$x$线和$a_j$插线板的$y$线之间的电阻是多少。规定插线板的树根节点不再插向其他插线板，且编号为$1$。

inputFormat:
第一行包含一个正整数$n$，表示插线板的个数。

接下来$4(n-1)$行，每4行为一个块。

第$i$块的第一行为一个整数$f_i$【注：原题如此。实际应该是$f_{i+1}$，下同】，表示编号为$i+1$的插线板的父亲为$f_i$【注：同上】插线板。

接下来一个$3\times3$的矩阵$g_{xy}$，第$x$行第$y$个数表示编号为$i+1$的插线板的$x$线和$f_i$【注：同上】的$y$线之间的电阻的**倒数**。

接下来一个整数$q$，表示$q$个操作数。

第一个整数位$k$，若$k=1$则接下来包含四个整数$a_i,x_i,x_j,g$，表示将$a_i$插线板的$x_i$线与$a_i$插线板的父亲$f_i$【注：原题如此。实际应该是$f_{a_i}$】的$x_j$线之间的电阻值改为$g$的倒数。保证$2≤a_i≤n$。

若$k=2$，则接下来包含四个整数$a_i,x_i,a_j,x_j$，表示询问$a_i$插线板的$x_i$线与$a_j$插线板的$x_j$线之间的电阻大小。保证$a_i≠a_j$。

outputFormat:
对每个询问，输出一行实数，表示两条线之间的电阻。

若|(选手输出-标准输出)/标准输出|$≤10^{-3}$，则被认为该电阻值正确，若所有电阻值皆正确，则可获得该测试点的得分。

hint:
对于所有测试数据，输入保证是一棵树。$0<$输入中电阻的倒数$≤10$。

测试点编号| 特点
:-:|:-:
$1\sim6$|$n≤100,q≤1000$，保证输入中只有查询没有修改
$7\sim10$|$n≤1000,q≤1000$，保证数据是一条链
$11\sim16$|$n≤10000,q≤10000$，保证树的高度不超过$30$
$17\sim20$|$n≤10000,q≤10000$


title: [CTSC2013] 组合子逻辑

description:
组合子逻辑是 Moses Schönfinkel 和 Haskell Curry 发明的一种符号系统，用于消除数理逻辑中对于变量的需要。本题考察一种与真实世界的组合子演算略有差别的组合子系统。

一个组合子项是下列形式之一：

$$P$$

$$(E_1\;E_2)$$

其中 $P$ 表示一个基本函数，$E_1$以及$E_2$表示一个组合子项(可以相同)。不满足以上形式表达式均非组合子项。

我们将一个组合子项 $E$ 的参数个数 $np(E)$如下：

$np(P)$ = 基本函数 $P$ 的参数个数；

$np((E_1\;E_2)) = np(E_1) - 1$。

本题中，我们用一个正整数同时表示一个基本函数，以及该基本函数的参数个数。

对于一个组合子项 $E$，如果它和它包含的所有组合子项的参数个数 $np$ 均为正整数，那么我们称这个 $E$ 为范式。

我们经常组合子项简化表示：如果一个组合子项$E$含有连续子序列$(… ((E_1\;E_2)\;E_3) …E_n)$ (其中 $n ≥ 3$)，其中$E_k$表示组合子项(可以是简化表示的)，那么将该部分替换为$(E_1\;E_2\;E_3 … E_n)$，其他部分不变，得到表达式 $E$ 的一个简化表示。一个组合子项可以被简化表示多次。

给定一个基本函数序列，问至少需要添加多少对括号，才能使得该表达式成为一个范式的简化表示(即满足范式的性质)；如果无论如何怎样添加括号，均不能得到范式的简化表示，输出$-1$。

inputFormat:
第一行包含一个正整数 $T$，表示有 $T$ 次询问。

接下来 $2T$ 行。

第 $2k$ 行有一个正整数$n_k$，表示第 $k$ 次询问的序列中基本函数的个数。

第 $2k + 1$ 行有$n_k$个正整数，其中第 $i$ 个整数表示序列中第 $i$ 个基本函数。

outputFormat: 输出 $T$ 行，每行一个整数，表示对应询问的输出结果。


title: [WC2011] 拼点游戏

description:
小 W 和小 Y 都很喜欢玩一种“拼点游戏”。游戏中两个人分别通过某种操作产生一个数作为自己的“点数”，点数大的一方获胜。“拼点游戏”的规则如下：

1. 游戏开始时，给定一个包含 $n$ 个元素的正整数序列 $U=(u_1,u_2,\cdots,u_n)$。
2. 定义 $U$ 的一个下标序列 $I=(i_1,i_2,\cdots,i_m)$ 是满足 $1\leq i_1<i_2<\cdots<i_m\leq n$ 的一个整数序列（ $m$ 可以为 0 ，即序列可以为空），并且其对应 $U$ 的子序列为 $V=(u_{i_1},u_{i_2},\cdots,u_{i_m})$。
3. 定义下标序列 $I=(i_1,i_2,\cdots,i_m)$ 对应的点数 $D(I)$ 为： $D(I)=\sum_{p=1}^m u_{i_p}\times (-1)^p$。
4. 进行游戏时两人分别选择一个下标序列，谁选择的下标序列对应的点数 $D(I)$ 大，谁就获胜。

然而在每次游戏中，小 W 总是能准确无误的算出点数最大的最优下标序列。为了让游戏更加具有竞技性，他们制定了下列额外规则：

Ex1. 小W可以选择一个非空区间 $[l,r]$，并将 $u_l,u_{l+1},\cdots,u_r$ 同时增加一个整数 $c$，产生的新序列将取代原序列 $U$。

Ex2. 当他们对于当前的 $U$ 序列进行一次“拼点游戏”时，允许小 Y 在小 W 选出最优下标序列 $I=(i_1,i_2,\cdots,i_m)$ 之后，对 $I_W$ 进行任意次修改操作。每次修改操作规则如下：

(1)任意选择一个正整数k满足݉ $2k+1\leq m$，以及两个非负整数 $z_1,z_2$ 满足 $i_{2k}+z_1<i_{2k+1}-z_2$；

(2)将 $i_{2k}$ 修改为 $i_{2k}+z_1$，将 $i_{2k+1}$ 修改为 $i_{2k+1}-z_2$。

若小 W 选出的下标序列 $I_W$ 经过小 Y 若干次修改操作之后所对应的点数小于等于 $0$，则小 Y 获胜。

现在给出小 W 所进行的 Ex1 操作的信息，请你对于每一次“拼点游戏”
，帮助他们计算：

a)小 W 一开始所能选出的最优下标序列对应的点数是多少？

b)小 Y 最少需要进行几次修改操作才能获胜？即使得 $D(I_W)\leq 0$。

inputFormat:
输入文件 joy.in 的第一行包含一个正整数 $T$，表示测试数据的组数。接下来为 $T$ 组数据。

每一组数据的第一行包含两个整数 $n$ 和 $q$，分别表示 $U$ 中的元素个数和事件个数。

接下来的一行，包含 $n$个 用一个空格隔开的正整数，第 $i$ 个整数为初始的序列中第 $i$ 个元素 $u_i$。

接下来 $q$ 行，每行代表一个事件（按事件发生顺序输入）。每行的第一个数非 $0$ 即 $1$，表示这个事件的类型。

若为 $0$ ：在 $0$ 之后还有三个整数 $l$，$r$ 和 $c$（这四个数之间均有一个空格）表示小 W 将 $u_l,u_{l+1},\cdots,u_r$ 增加 $c$；

若为 $1$：表示两人进行了一次“拼点游戏”，你需要输出相应的结果。

输入数据保证序列 $U$ 中的所有元素总是正整数。

outputFormat:
输出文件为joy.out。对于每一组测试数据，依次对每一次“拼点游戏”输出一行包含两个由一个空格隔开的整数 $D_{max}$ 和 $X$，其中

$D_{max}$ 为对于当前序列 $U$，小 W 所能选出的最优下标序列所对应的点数；

$X$ 表示小 Y 最少需要进行几次修改操作才能获胜。如果小 Y 不论多少次操作都无法获胜，则输出```-1```。

数据保证最优下标序列总是唯一的。

hint:
【评分标准】

一个测试点包含多组测试数据，对于该测试点：

如果所有的 $D_{max}$ 均正确但某个 $X$ 不正确，则可以得到3分；

如果所有的 $X$ 均正确但某个 $D_{max}$ 不正确，则可以得到7分；

如果所有回答均正确，则可以得到 10 分。

【样例说明】

输入数据包含两组测试数据。

在第一组测试数据中：第一次“拼点游戏”时，最优下标序列为 $(1,2,4,5)$，小 Y 只需要进行一次修改操作：选择 $k=1$，以及非负整数 $z_1=1,z_2=0$。这样经过修改操作之后下标序列将变为 $(1,3,4,5)$，小 Y 获胜。

第三次“拼点游戏”时，序列 $U$ 为 $(9,8,6,5,3)$，小 W 所选择的最优下标序列为空序列，所产生的点数为 $0$。在这种情况下，小 Y 无法进行任何修改操作（也无需进行任何修改操作），此时小 Y 已经直接获胜。

【数据规模】

对于 10% 的数据满足 $n,q\leq 13$；

对于 30% 的数据满足 $n,q\leq 1000$；

对于另外 20% 的数据满足 $T=1$ 且 $n\leq 40000$；

对于 100% 的数据满足 $T\leq 3$ 且 $n,q\leq 10^5$，同时初始序列 $U$ 满足 $0 <u_i< 2^{31}$，$|c|<10^5$。


title: [CTSC2013] 因式分解

description:
通过代数基本定理，我们知道若计算重根，一个 n 次的多项式在复数域内恰好有 n 个零点(函数值为 0 的点)。现给定一个整系数多项式 F[x]，它的 n 个零点恰好都是有理数(即可以写成两个整数相除的形式)；同时，若我们把它所有的非零零点(函数自变量不为 0，函数值为 0)去重，则可以得到 r 个互不相同的非零零点，其中第 i 个非零零点可以被表示成下式：

$$sgn_i \times \frac{q_i}{p_i}$$

式中$sgn_i$表示第 i 个零点的符号，$p_i$和$q_i$为互质的两个正整数。

现在告诉你 F[x]，要求你输出将他因式分解后的形式。

inputFormat:
输入只有一行，包含多项式 F[x]。

多项式一定是如下的形式：

$a_n x$^$n + a_{n-1}x$^${n - 1} + ⋯ a_1x + a_0$

次数一定为从高到低，其中$a_i$为整数，并且若$a_i$为 0，则省略该项，若$a_i$为负数，则省略之前的加号，若$a_i$的绝对值为 1 且 i 不为 0，则不输出 1，并且保证$a_n$不为 0.

详见样例输入。

outputFormat:
输出一行，表示因式分解后的形式，格式如下：

$a_n (x + u_1/v_1)$^$t_1(x + u_2/v_2)$^$t_2 … (x + u_s/v_s)$^$t_s$

其中 u，v 互质，且 v 为正整数。

其中$u_i/v_i$从大到小排列，若$u_i/v_i = 0$ 则该项为 $x$^$t_i$，若$u_i/v_i$为负数，则省略加号，若$v_i$为 $1$，则省略$/v_i$。

若$t_i$为 $1$ 则省略^$t_i$。

若$a_n$为$±1$ 则将 $1$ 省略。

详见样例输出。


title: [CTSC2013] 猴子大战

description:
小 Q 和小 M 最近发明了一种卡牌游戏，叫猴子大战。

游戏最初小 Q 和小 M 各会取得一部分猴子牌。每局游戏，他们两个需要分别等概率地从自己的猴子牌中抽取一张进行战斗。获胜的一方将获得双方的猴子牌。如果一方获得了所有的猴子牌，则该方获得整场游戏的胜利。否则游戏将一直进行下去。

在进行了若干场比赛以后，小 Q 和小 M 算出了一张胜率表，为每张猴子牌之间进行战斗双方获胜的概率。由于每场战斗一定会决出胜负，而且胜率不受先后顺序的影响，因此对于任意的两张猴子牌 A 和 B，A 战胜 B 的概率加 B 战胜 A 的概率为 $1$。

由于自己老是输给小 M，小 Q 开始怀疑自己每次拿到的猴子牌是否能获得胜利。他希望求出自己拿到的每种猴子牌组合的获胜的概率。

由于小 Q 接下来还有在 CD 市体育中心数以万计的运动计划，因此这个问题只能交给你来解决了。

inputFormat:
输入的第一行包含两个正整数 $n$ 和 $m$，表示猴子牌的总张数和需要求的猴子牌组合的个数。

接下来有 $n$ 行，每行包含 $n$ 个实数，每个实数保留了两位小数。这 $n$ 行中，其中第 $i$ 行第 $j$ 列的数为$P_{i,j}$，表示第 i 张猴子牌战胜第 $j$ 张猴子牌的概率。保证$P_{i,j} + P_{j,i} = 1$。特别地，$P_{i,i} = 0.5$，没有特殊意义。

最后有 $m$ 行。每行包含一个长度为 $n$ 的无空格分隔的 $01$ 串，表示一个猴子牌的组合。其中第 $i$ 个字符如果为 $0$，表示最初第 $i$ 张牌在小 M 处，否则表示在小 Q 处。

outputFormat: 输出 $m$ 行，每行一个实数，四舍五入保留八位小数（请强制输出八位浮点数），依次表示每个给定的猴子牌组合下小 Q 获胜的概率。

hint:
**【评分方法】**

你的答案的每一行如果与我们给定的参考答案的差别均不超过 $2 \times 10^{-6}$，则获得该测试点的得分，否则不得分。

参考答案保证与真实值的差别不超过 $10 ^ {-8}$，因此如果你输出的答案保证与真实值差别不超过 $2 \times 10^{-6}\sim 10 ^ {-8}$，才能保证正确。

**【数据规模及约定】**

对于每组数据，$n$ 的取值如下

测试点编号|$n$|测试点编号|$n$
:-:|:-:|:-:|:-:
1|$n = 2$|6|$n = 20$
2|$n = 5$|7|$n = 40$
3|$n = 7$|8|$n = 60$
4|$n = 8$|9|$n = 80$
5|$n = 10$|10|$n = 100$

对于 100%的数据，保证 $1 ≤ n ≤ 100$，$1 ≤ m ≤ n^2$。$0 ≤ P_{i,j} ≤ 1$，$P_{i,j}$恰好包含 $2$ 位小数，且 $P_{i,j} + P_{j,i} = 1$.表示猴子牌组合的 $01$ 串长度均为 $n$，且不含其他字符。


title: [WC2007] 疯狂赛车

background:
布布是一个《泡泡堂》高手，拥有着近乎完美的战绩。他擅长很多地图，例如“小区10”、“海盗14”、“大海02”等等，不过他最喜欢的地图是“赛车”。

在赛车地图中，每个玩家将得到一辆赛车，从起点出发，比赛谁最先到达终点。

description:
在地图中，包括有障碍、加油站、赛车跑道与沙地。障碍不可通过，并且赛车在赛车跑道与沙地上的行进速度是不一样的。

现在我们来考虑一个简化版的赛车游戏。在这个简化版本的赛车游戏中：

* 比赛在一个无限大的沙地平面上举行。

* 赛道是一个从原点出发、由$n$条线段首尾相接组成的折线。

* 出于安全考虑，赛道不会自交（即折线中的任何两条线段，相邻两条线段有且仅有一个公共点，其他任意两条线段均无公共点）。

* 赛车在赛道上的速度为$v_a$，在沙地上的速度为$v_b$，且满足 $v_a\geq v_b$。

* 为了增加比赛的挑战性，在赛道上逆向行驶是允许的。

布布是一个操作非常精确的选手，他总能按照预想的道路行进至终点，但是他不知道哪个才是最快的路线，聪明的你，能帮助他么？

inputFormat:
输入文件racing.in的第1行包含一个整数$n$，表示赛道一共有$n$段；第2行包含两个实数$v_a$与$v_b$，分别表示赛车在赛道上与沙地中的行进速度。

接下来的$n$行，每行包含两个整数$x_i$与$y_i$，依次表示赛道的每一个转折点。即赛道的第一个线段是$(0,0)\rightarrow (x_1 , y_1)$，第二条线段是$(x_1 , y_1)\rightarrow ( x_2 , y_2)$，依次类推。其中$(x_n , y_n)$为终点。

outputFormat: 输出文件racing.out仅包含一个实数，表示从起点到终点最少所需时间。精确到小数点后6位。

hint:
【评分标准】

每一组数据单独评分，对于每一组数据，你的得分按照如下公式计算：

$$YourScore=\begin{cases}10 &  |YourAnswer-OurAnswer|\leq 0.0001\\  5  & |YourAnswer-OurAnswer|\leq 0.01 \\ 0 &    Otherwise \end{cases}$$

【数据规模】

对于20%的数据，赛道的折线段平行于坐标轴。

对于40%的数据，$n\leq 50$ 。

对于100%的数据，$n\leq 1000$ ，$1\leq v_b\leq v_a\leq 20 $。

所有的坐标都在$[-10^6 , 10^6]$内。


title: [CTSC2011] 杀菌计划

background: 输入数据下发链接: https://pan.baidu.com/s/1ltIqAf8bdtnAFrFTnVtgHA

description:
栋栋有一个凸多面体形状的漂亮盒子，这个盒子的每个面都由形状为凸多边形的透明玻璃薄壁组成。

每隔一段时间，栋栋就要使用一个激光发射器给他的盒子杀菌。激光发射器能发射出一束激光，当激光照射到盒子的玻璃薄壁时，会把薄壁内外两面的细菌杀死，同时有大量光线透射过玻璃，少量光线被玻璃反射。透射过玻璃的光线沿原方向前进，反射的光线遵循光线的镜面反射定理，即在反射时反射光线、入射光线和镜面的法线在同一平面内，反射光线与入射光线分居法线两侧，反射角（反射光线与法线的夹角）等于入射角（入射光线与法线的夹角）。

我们认为激光被玻璃反射k 次后的能量不足以杀死细菌（即使有多个这样的光线同时照射在玻璃薄壁上也不能杀死细菌），而k 次反射前激光照射到的细菌都会被杀死。

激光发射器的发射口是三角形的，当发射激光时，整个发射口都会发出激光。

给定盒子和激光发射器的位置，栋栋想知道，盒子的玻璃薄壁上有多大面积
的细菌被杀死了。由于盒子的内外两面的细菌必然是同时被杀死或者同时不被杀死，所以只要算出外面被杀死的细菌面积即可。

注意，激光或经过反射的激光可能与某些表面平行，但本题的数据保证激光或经过反射的激光不会照射到与之平行的表面。

inputFormat:
本题是一道提交答案型试题，所有输入数据box1.in ~ box10.in 已放在了试题的目录下。每个输入数据满足下面的输入格式，每两个数之间用一个空格隔开：

输入的第一行包含三个整数$n, m, k$，分别表示盒子的顶点数、盒子的面数和光线的反射次数。

接下来$n$ 行，第$i$ 行包含三个实数$x_i, y_i, z_i$，表示盒子第$i$ 个顶点的坐标。

接下来$m$ 行，每行描述盒子的一个表面，每行第一个数$t_j$，表示该表面的多边形的顶点个数，接下来$t_j$ 个整数，表示这$t_j$ 个顶点对应的盒子顶点的编号，这些编号按顶点在面上的顺时针或逆时针顺序给出。

接下来三行，每行$3$ 个整数$x, y, z$，分别表示激光发射器发射口的坐标。

接下来$1$ 行，包含3 个整数$Δx, Δy, Δz$，表示出射光线的方向是沿着向量$(Δx, Δy, Δz)$的方向。

outputFormat:
针对给定的10 个输入文件box1.in ~ box10.in，你需要分别提交你的输出文
件 box1.out ~ box10.out。每个输出文件包含一个实数，四舍五入保留两位小数，表示被杀死的细菌的面积。当一个表面被多次照射到时，这个表面的面积只计算一次。

hint:
样例数据如下图所示，盒子是一个正方体的形状，激光从右边照射过来，照
射到右侧面上，并透射过右侧面照射到左侧面上，将左右两侧面上的两个三角形区域的细菌杀死。在照射到左右侧面后激光都会发生反射，但由k=1，反射光线已不能将细菌杀死，所以不用考虑。

![](https://cdn.luogu.com.cn/upload/pic/17995.png)


title: [CTSC2015] 葱

description:
小葱和小绪是一对好朋友，自从小葱11连出了1UR2SR之后，小绪就觉得小葱的人品特别好，于是小绪给小葱出了一道题来测试小葱的人品。

小绪首先在平面上画了$N$个点，分别是$P_1,P_2,...,P_N$。

小绪把这$N个点$顺次相连，即连接$(P_1,P_2),(P_2,P_3),...,(P_{N-1},P_N)$，得到$N-1$条线段。

之后小绪每次在平面上画出一条直线，然后问小葱这条直线与多少条线段相交。特别的，在线段端点处相交算作相交，直线完全覆盖线段时也算作相交。 这样的问题自然难不倒小葱，小葱只需要凭自己的人品用直觉就能给出正确的答案。

小绪想测试小葱的人品究竟有多好，于是他加大了问题的难度： 除了每次询问以外，小绪会不时地讲一个新的点$P$插入到$P_i$和$P_{i+1}$之间，然后按照顺序对所有的点重新标记下标，即在$P_i$之后的点的下标会依次增加，而点$P$会变成新的点$P_{i+1}$。

特别的，点$P$也可以插入到第一个点之前或最后一个点之后。

人品超级好的小葱依旧能够轻松的给出答案，于是小绪又进一步提高了难度：

每次插入或提问之后，小绪都将操作后的所有线段记录了下来，称作一个历史版本。历史版本$T$表示在第$T$次操作后得到的历史版本。

插入新点的操作改为了在某一个历史版本$T$的基础上，插入一个点$P$，并得到一个新的历史版本。

小绪对小葱的提问改为了对于一个历史版本$T$，给出一条直线，询问这条直线会与多少条线段相交。

小葱虽然人品很好，但面对这样的问题却也束手无策了，他只好找到来参加CTSC的你，请你来帮他解决这个问题。

inputFormat:
第一行两个整数$N,M,C$，表示一开始的点数和总共的操作数，以及数据是否加密。

如果$C=1$，那么代表数据被加密过，每次询问操作中的$X_0,Y_0,X,Y$以及插入操作中的$X,Y$都是被加密过的数据，你需要将它们异或last_ans从而得到正确的数据，其中last_ans是上一次询问的答案，刚开始last_ans=0。

接下来$N$行每行两个整数，其中第$i$行的两个整数表示$P_i$的横坐标和纵坐标。

接下来$M$行，表示小绪的$M$次操作，其中第$i$行（从$1$开始标号）操作后得到的结果为历史版本$i$。

对于每次操作，首先会有一个字母代表小绪的这次操作的操作类型。

如果这个字母是$'H'$，代表本次操作为一次询问操作。接下来会有五个整数$T,X_0,Y_0,X,Y$，代表在历史版本$T$的情况下，小绪给出一条经过$(X_0,Y_0)$，方向为$(X,Y)$的直线，小葱要回答出它会和多少条直线相交。

如果这个字母是$'Z'$，代表本次操作为一次插入操作。接下来会有四个数$T,i,X,Y$，代表小绪在历史版本$T$的基础上，在$P_i$后面插入了一个坐标为$(X,Y)$的点。特别地，如果$i=0$，表示该点在$P_1$之前。

outputFormat: 要求对每一次询问操作，输出一行一个整数代表小葱应该回答的正确答案。

hint:
样例解释1：

对于第三次询问，直线完全覆盖了线段，小绪会认为这也算相交。

数据规模和约定：

保证每次询问操作的$T$一定小于等于当前操作的数量，所有输入数据均为整数。

有以下$4$类特殊数据，它们两两没有交集：

1. 对于10%的数据，保证$1≤N,M≤1000$；

2. 对于15%的数据，保证对于第$i$次操作，$T=i-1$；

3. 对于15%的数据，保证$C=0$且不存在修改操作；

4. 对于15%的数据，对于询问操作，保证$Y=0$（加密过的数据指解密后的$Y$），即给出的直线平行于$x$轴。

以上数据还保证$1≤N,M≤5*10^4$。

对于100%的数据，保证$1≤N,M≤10^5$，所有的坐标范围在$[-10^8,10^8]$内，且每组数据中所有询问的答案总和不超过$10^6$，插入操作的次数不会超过$5*10^4$。注意这些线段可能会互相相交。


title: [CTSC2015] 性别改造计划

description:
21 世纪是生命科学的世纪。人类投入了大量人力物力研究生命科学，旨在对各类生物的生存机理产生更加深入的理解，以更好地了解人类自身，提高生活质量。Q 国政府首先在绵羊中开展了性别改造研究，希望通过基因重组改变性别的方式增强整个绵羊种群的生存能力。若此计划能够顺利研究成功，人类将掌握随意改变动物性别的黑科技，这将是生命科学研究史上一个重要的里程碑。

Q 国政府从绵羊群中挑出 $M$ 只绵羊作为实验样本，这 $M$ 只绵羊中存在 $K$ 条长度为 $N$ 的单一性别的血缘链。所谓 “血缘链” 是指的一条由父（母）子（女）关系组成的链，比如 “爷爷 - 爸爸 - 儿子” 就是一条血缘链。“单一性别” 的意思是每条血缘链中所有个体的性别均一致，同为雄性或同为雌性。血缘链长度指的是一条血缘链中个体的数量，比如 “爷爷 - 爸爸 - 儿子” 是一条长度为 $3$ 的血缘链。这 $K$ 条血缘链并不相交。

注意并不是每只绵羊都必须属于一条血缘链，有些绵羊可能不属于任何血缘链，因此 $N\times K\leq M$。除去血缘链外，同辈绵羊还会有 “繁衍关系” 的存在。两只异性绵羊如果曾经繁殖过后代，那么它们之间就会产生 “繁衍关系”。注意繁衍关系只会出现在同辈异性绵羊个体之间，这里 “同辈” 表示两只绵羊的辈份相同，即绵羊只会与它的兄弟姐妹辈产生 “繁衍关系”，而不会与父母或子女或其他更远的辈份之间产生 “繁衍关系”。

对绵羊进行性别修改需要花费巨大的实验开销，修改绵羊 $i$ 的性别需要花费 $c_i$ 的修改代价。除此以外，修改绵羊性别还会对繁衍关系的稳定度产生影响：每对繁衍关系 $j$ 有初始稳定度 $b_j$ 和衰减系数 $d_j$，当所有的性别修改操作完成后，若双方性别均未改变，则此关系稳定度 $s_j = b_j$，若双方性别互换，则稳定度 $s_j = \lfloor b_jd_j\rfloor$，其他情况下稳定度 $s_j = 0$。

给定每只绵羊的性别，性别修改代价，所有血缘链关系很繁衍关系，Q 国政府希望你来设计一套性别改造方案，使总收益最大。收益计算方式如下：

$$
P = \lfloor 10 \ln(1 + A) \rfloor \times S - C
$$

其中 $A$ 为改造后血缘链相邻两者为异性的情况数量，$S$ 为改造后繁衍关系稳定度之和，即 $S = \sum\limits_js_j$，$C$ 为修改绵羊性别带来的代价之和，即 $C = \sum\limits_ic_i$。

inputFormat:
第一行包含四个非负整数 $N, K, M, P$，分别为血缘链的长度，血缘链的数量，实验样本中的总绵羊数和繁衍关系的数量。

第二行为一个 $M$ 个字符的字符串，每个字符为 `M` 或 `F`，描述了这 $M$ 只绵羊的初始性别。`M` 表示雄性，`F` 表示雌性。

第三行 $M$ 个正整数 $c_i$，表示修改每只绵羊性别的代价。

下面 $K$ 行每行 $N$ 个整数，分别描述这 $K$ 个血缘链中绵羊编号（所有绵羊用 $1$ 到 $M$ 的整数编号），保证每条链中的绵羊均为同性，且链互不交叠。

下面 $P$ 行每行三个整数 $x, y, b$ 和一个实数 $d$，表示绵羊 $x$ 与绵羊 $y$ 存在繁衍关系，且初始关系稳定度为 $b$，衰减系数为 $d$。

保证 $x$ 与 $y$ 的初始性别不同，$x$ 和 $y$ 为同辈，同一条关系只会在数据中描述一次。

outputFormat: 仅包含一行一个整数，表示改造计划的最大收益。

hint:
**【样例解释】**

改性别为 `MMFFFM`。收益为 $\lfloor 10 \ln(1 + 2) \rfloor \times(20 + 18) - (10 + 10) = 360$。$A = 2$ 是因为血缘链 $1 - 2 - 3$ 中 $2$ 与 $3$ 性别的不同，血缘链 $4 - 5 - 6$ 中 $5$ 与 $6$ 的性别不同。

**【数据范围】**

对于 $10\%$ 的数据，满足 $M\leq 20$。

对于 $10\%$ 的数据，满足 $d_j = 0$。

对于 $10\%$ 的数据，满足 $d_j = 0.5$。

上述三类数据两两没有交集。

对于 $100\%$ 的数据，$1\leq N\leq 50$，$1\leq K\leq 4$，$1\leq M\leq 10 ^ 3$，$1\leq P\leq 10 ^ 4$，$0 \leq d_j\leq 1$，$0\leq b_j, c_i \le 10 ^ 4$，$d_j$ 的小数位数不超过 $6$。


title: [CTSC2015] 日程管理

description:
幽香是幻想乡中一个非常有地位的人。她日理万机，事务繁多，反倒自己已经快管理不过来了。于是他决定开发一个日程管理软件来帮助自己管理任务。

对于每个任务 $i$ 有一个对应的截止日期 $t_i$ 以及收益 $p_i$，表示若幽香能在不晚于第 $t_i$ 天完成这个任务，便可以得到 $p_i$ 的收益。幽香办事的能力非常强，任何任务都可以用恰好一天的时间做完。但由于任务实在太多了，有时候并不能完成所有任务，于是幽香会想知道这个情况下，完成任务可以给她带来的最大的累积收益是多少。

由于幻想乡的人们十分善变，任务总是不断发生着变化。幽香希望这个管理软件还能够支持插入一个任务，和删除一个任务的操作。

具体的说，幽香希望支持以下 $2$ 个操作：

1. `ADD t p`：表示新添一个截止日期为 $t$，收益为 $p$ 的任务。

2. `DEL t p`：表示删除一个截止日期为 $t$，收益为 $p$ 的任务。如果有多个这样的任务，只删除一个。数据保证这样的任务一定存在。

在每次操作执行完毕后，你都需要输出能够完成的任务的最大收益和。

幽香一共有 $T$ 天需要安排，从第 $1$ 天到第 $T$ 天。你能帮助他写出这个高效率的软件吗？

inputFormat:
第一行有两个整数 $T$ 和 $Q$，表示天数和操作的个数。

接下来 $Q$ 行，其中第 $i$ 行表示第 $i$ 个操作，形式为 `ADD t p` 或 `DEL t p`，其具体意义如题面所述。

outputFormat: 对每一次操作，输出一个整数在执行完该操作后幽香能够获得的最大收益和。

hint:
数据保证，$1\le T,Q\le 3\times 10^5$。

$\text{Statement fixed by @Starrykiller.}$


title: [CTSC2009] 移民站选址

description:
2323年，随着科技的发展以及地球日趋严重的人口压力，人类开始大规模向火星移民。令人欣慰的是，移民工程的第一步取得了巨大的成功，已经在火星表面建立了$N$个移民站，其中第i个移民站的坐标是$(u_i, v_i)$。但是在进行后续的移民工作时，人们遇到了一个严峻的问题：如何选择新建的移民站的地址。经过调查确定，需要在火星上新建$M$个移民站，已知原有的第$i$个移民站和新建的第$j$个移民站之间信息传输的流量是$A_{i,j}$，新建的第$j$个移民站和第$k$个移民站之间信息传输的流量是$B_{j,k}$，同时假定，将一个单位流量的信息传输一个单位距离的费用是$1$，这里的距离定义为曼哈顿距离。两个点$(x_1, y_1)$和$(x_2, y_2)$的曼哈顿距离定义如下：

$$ \mathrm{ManhattanDist}( (x_1, y_1), (x_2, y_2) ) = |x_1 - x_2| + |y_1 - y_2| $$

现在的问题是，给定原有的$N$个移民站的地址和信息流量传输矩阵$A$、$B$，需要你为这$M$个新的移民站选择地址，使得信息传输总费用最小。

inputFormat: 输入文件为*locate1.in~locate10.in*，第一行为两个整数$N$、$M$，表示原有移民站的数目和需要新建的移民站的数目。接下来的N行每行包含两个整数，表示原有的移民站的坐标；接下来$N$行每行包含$M$个整数，表示信息流量传输矩阵$A$；最后$M-1$行中，第$i$行包含$M-i$个整数，其中的第$j$个表示$B_{i,i+j}$。

outputFormat: 输出文件为*locate1.out~locate10.out*，*locate?.out*对应*locate?.in*的答案。输出的第一行为一个整数，表示你所计算出的信息传输费用。接下来的$M$行每行包含两个整数，其中第$i$行表示第$i$个新建的移民站的坐标。

hint:
本题输入数据下载：[百度网盘](https://pan.baidu.com/s/1hEbcB45kL25wbXqEeew7Yg)

**【评分标准】**

每个测试点单独评分。

对于每一个测试点，如果你给出的输出文件不合法，如文件格式错误、输出
解不符合要求等，该测试点得 0 分。否则设你的输出答案长度为 ans，对于不同的测试点，我们还设有 9 个评分相关的常数 c1 ≤ c2 ≤ c3 ≤ c4 ≤ c5 ≤ c6
≤ c7 ≤ c8 ≤ c9 ≤ c10，你在该测试点中的得分由下列陈述得出：

- 如果 ans > c10，得0分。
- 如果 ans ≤ c10，得1分。
- 如果 ans ≤ c9，得2分。
- 如果 ans ≤ c8，得3分。
- 如果 ans ≤ c7，得4分。
- 如果 ans ≤ c6，得5分。
- 如果 ans ≤ c5，得6分。
- 如果 ans ≤ c4，得7分。
- 如果 ans ≤ c3，得8分。
- 如果 ans ≤ c2，得9分。
- 如果 ans ≤ c1，得10分。
- ~~如果 ans < c1，得12分。~~
- 如果满足多个条件，取得分最大者为最终得分。

**【特别提示】**

请妥善保存输入文件*locate\*.in* 和你的输出*locate\*.out*，及时备份，以免误删。☺


title: [CTSC2009] 纷繁世界

background:
这是一个纷繁复杂的世界。

某一天清晨你起床很迟，没有吃上早饭。于是你骑着自行车去超市，但是你又发现商店的工作人员已经重新贴上了价格标签，零食价格都涨了50%。你一怒之下就这样饿了一个上午……

当然，事情也许完全不会这样发展。

某一天清晨你起床比较迟，但还是没有吃上早饭。于是你骑着自行车去超市，恰好商店的工作人员还没有把涨价后的价格标签贴在零食上。于是你顺利的买了一些早餐然后逍遥而去……

或许你会起得更早，也或许商店的工作人员会迟到。

有时候，人们只是按照预想的顺序去完成一些事情，不过可能有一些事件，它们发生时间的前后顺序会影响世界的发展。

比如，如果商店只有一个西瓜，你想买，我也想买，那么我们买西瓜的先后顺序就会直接影响到谁最后能够买到西瓜。

这样一个复杂的世界，分析它的运行规律是一件非常重要的工作，也是你所要研究的。

description:
简单起见，假定总共有$N$个人以及$M$种不同类型事件。 定义事件之间的二元关系“相关”：

- 相关关系是一个二元关系，就是说我们只能定义两种类型的事件间是否相关；
- 同一种类型的事件之间一定是相关的；
- 若事件$x$与事件$y$是相关的，那么事件$y$与事件$x$也一定是相关的；

令$Q_i = (Q_{i, 1}, Q_{i, 2}, \cdots, Q_{i, C_i})$表示第$i$个人计划完成的事件序列（称为计划序列），$C_i$表示$Q_i$的长度。$Q_i$中每个事件$Q_{i,j}$都是$M$种事件中的某一种，且同一种类型的事件可以发生多次。

随着时间的推移每个计划序列中的事件都会发生一次且恰好一次；为了简单起见，不会有任何两个事件发生在同一时刻。

为了描述事件的发生顺序，定义$P = (Q_{i_1, j_1}, Q_{i_2, j_2}, \cdots, Q_{i_l, j_l})$为世界的一条发展轨迹，$P$是满足如下条件的有序序列：

1. 对于每个人，计划序列中的每个事件$Q_{i,j}$都在$P$出现一次且恰好一次；
2. 对于属于同一个计划序列的两个事件$Q_{i,j_1}$和$Q_{i,j_2}$（$1 \leq j_1 < j_2 \leq C_i$），$Q_{i,j_1}$一定发生在$Q_{i,j_2}$之前（也就是在$P$中位于更靠前的位置）；

两条轨迹$P_1$和$P_2$被定义为本质不同的，当且仅当存在两个相关的事件$Q_{i,j}$和$Q_{u,v}$，他们在$P_1$和$P_2$中发生的先后顺序不同，也就是说，如果在$P_1$中$Q_{i,j}$发生在$Q_{u,v}$之前且在$P_2$中$Q_{i,j}$发生在$Q_{u,v}$之后，那么$P_1$和$P_2$就是本质不同的；如果在$P_1$中$Q_{i,j}$发生在$Q_{u,v}$之后且在$P_2$中$Q_{i,j}$发生在$Q_{u,v}$之前，那么$P_1$和$P_2$也是本质不同的；

注意：本质相同具有传递性，即若$P_1$与$P_2$本质相同且$P_2$与$P_3$本质相同，那么$P_1$与$P_3$一定也本质相同。

给定$N, M$、每个人计划序列以及事件之间的相关关系。你需要计算一共有多少种本质不同的世界运行轨迹。

inputFormat:
输入文件*world.in*第一行包括一个整数，表示人数$N$。

输入文件第二行包括一个整数，表示事件种类数$M$，所有类型的事件按照$0$至$M - 1$编号。

接下来依次给出每个人的计划序列的描述，对于第$i$个人：

首先一行一个整数表示序列长度$C_i$。

第二行包含$C_i$个整数，依次给出$Q_i$中的每个事件$Q_{i,j}$。

最后$M$行输入一个$M$行$M$列的矩阵$dep$用来描述相关关系，每行包含$M$个整数，都是$0$或者$1$。$dep(i,j)$表示矩阵自上往下的第$i$行，自左往右的第$j$列所包含的整数。若$dep(i, j)$的值为$1$，那么第$i$类事件和第$j$类事件就是相关的，否则这两类事件不相关。

outputFormat: 输出文件*world.out*只有一行，一个整数表示本质不同的世界轨迹数$T$。