The $N (2 <= N <= 10,000)$ cows are so excited: it’s prom night! They are dressed in their finest gowns, complete with corsages and new shoes. They know that tonight they will each try to perform the Round Dance.

Only cows can perform the Round Dance which requires a set of ropes and a circular stock tank. To begin, the cows line up around a circular stock tank and number themselves in clockwise order consecutively from 1..N. Each cow faces the tank so she can see the other dancers.

Consider the two networks shown below. Assuming that data moves around these networks only between directly connected nodes on a peer-to-peer basis, a failure of a single node, $3$, in the network on the left would prevent some of the still available nodes from communicating with each other. Nodes $1$ and $2$ could still communicate with each other as could nodes $4$ and $5$, but communication between any other pairs of nodes would no longer be possible.

为了从F($1 \leq F \leq 5000$)个草场中的一个走到另一个，贝茜和她的同伴们有时不得不路过一些她们讨厌的可怕的树．奶牛们已经厌倦了被迫走某一条路，所以她们想建一些新路，使每一对草场之间都会至少有两条相互分离的路径，这样她们就有多一些选择．

每对草场之间已经有至少一条路径．给出所有R($F-1 \leq R \leq 10000$)条双向路的描述，每条路连接了两个不同的草场，请计算最少的新建道路的数量, 路径由若干道路首尾相连而成．两条路径相互分离，是指两条路径没有一条重合的道路．但是，两条分离的路径上可以有一些相同的草场． 对于同一对草场之间，可能已经有两条不同的道路，你也可以在它们之间再建一条道路，作为另一条不同的道路．

有一天一位灵魂画师画了一张图，现在要你找出欧拉回路，即在图中找一个环使得每条边都在环上出现恰好一次。
一共两个子任务：

1. 这张图是无向图。（$50$ 分）
2. 这张图是有向图。（$50$ 分）

$AA$ 树是 $Arne Andersson$ 教授在他的论文 $”Balanced search trees made simple”$ 中介绍的一个红黑树变种，设计的目的是减少 $RB$ 树考虑的 $cases$。

通常情况下，我们可以使用函数 $toupper()$ 和 $tolower()$ 来实现字母大小写的转化，但在需要常数优化的情况下，这是较慢的。

Given a string of length at most $100,000$ consist of alphabets and numbers. Output the suffix array of the string.
A suffix array is an array of integers giving the starting positions $(0-based)$ of suffixes of a string in lexicographical order. Consider a string $”abracadabra0AbRa4Cad14abra”$. The size of the suffix array is equal to the length of the string. Below is the list of $26$ suffixes of the string along with its starting position sorted in lexicographical order:

$FJ$ 打算带他的 $N(1 \leq N \leq 30,000)$ 头奶牛去参加一年一度的“全美农场主大奖赛”。在这场比赛中，每个参赛者都必须让他的奶牛排成一列，然后领她们从裁判席前依次走过。 今年，竞赛委员会在接受队伍报名时，采用了一种新的登记规则：他们把所有队伍中奶牛名字的首字母取出，按它们对应奶牛在队伍中的次序排成一列（比如说，如果 $FJ$ 带去的奶牛依次为 Bessie、Sylvia、Dora，登记人员就把这支队伍登记为 $BSD$）。登记结束后，组委会将所有队伍的登记名称按字典序升序排列，就得到了他们的出场顺序。 $FJ$ 最近有一大堆事情，因此他不打算在这个比赛上浪费过多的时间，也就是说，他想尽可能早地出场。于是，他打算把奶牛们预先设计好的队型重新调整一下。 $FJ$ 的调整方法是这样的：每次，他在原来队列的首端或是尾端牵出一头奶牛，把她安排到新队列的尾部，然后对剩余的奶牛队列重复以上的操作，直到所有奶牛都被插到了新的队列里。这样得到的队列，就是FJ拉去登记的最终的奶牛队列。 接下来的事情就交给你了：对于给定的奶牛们的初始位置，计算出按照 $FJ$ 的调整规则所可能得到的字典序最小的队列。

把一个字符串 $S$ 排成一圈，从每个字符开始读一圈，把每次读到的字符串排序，按顺序将每个串的最后一个字符排成一个新字符串，求新字符串。

链接

BZOJ1031

定义

字符串

字符串 $s$ 连续的一段字符组成的串叫做字符串，更广义地，任何一个由可比较大小的元素组成的数组都可称为字符串。字符串的下标从 $0$ 开始，长度为 $length(s)$。

后缀

后缀：$suffix(i)$ 表示字符串 $s$ 从第 $i$ 个位置开始的后缀，即由 $s[i]$ ~ $s[n - 1]$ 组成的子串。

排名系统通常要应付三种请求：上传一条新的得分记录、查询某个玩家的当前排名以及返回某个区段内的排名记录。当某个玩家上传自己最新的得分记录时，他原有的得分记录会被删除。为了减轻服务器负担，在返回某个区段内的排名记录时，最多返回$10$ 条记录。

小 $A$ 住在魔法森林里,魔法森林的道路构成了一个 $n$ 个节点的树,在这棵树的每个节点上都生长了蘑菇。蘑菇有若干种不同的颜色。
现在小 $M$ 要到小 $A$ 那里去。小 $M$ 想要炼制一种药剂需要很多不同颜色的蘑菇。
她想要在去小 $A$ 家的路上采摘尽可能多不同颜色的蘑菇。然而,她忘了小 $A$ 家在那里。她假设小 $A$ 家会等概率随机在 $n$ 个点的某一个上。好在,小 $M$ 可以从任意一个节点出发来走到小 $A$ 家。
现在小 $M$ 想要知道,对于每一个节点,假如她从这个节点出发,采摘到蘑菇种数的期望是多少。为了避免不必要的麻烦,请将答案 $*n$ 之后输出。

对于一个非空集合{$a_i$},我们称一个集合是 $magical$ 的,当且仅当它满足以下两个条件。

1:$a_1$ & $a_2$ &…& $a_n$ =0(&表示 $and$)

2:{$a_i$} 的任意一个除它本身外的非空子集不满足1。

小 $A$ 有一个很大很大的集合。很显然这个集合的子集数量是一个天文数字。

小 $A$ 现在想要知道这个集合的 magical 的非空子集数量是多少。

为了防止不必要的麻烦,请将答案 $mod$ $1e9+7$ 后输出。

JPY 精进了生物以后准备再去精进一下通技,于是就向通技竞赛(我也不知道是什么)的同学去请教了各种问题。通技竞赛的同学非常耐心,为他解答了各种问题。过了不久，JPY 感觉自己通技可以虐场了。于是通技竞赛的同学就给他出了一个问题:一个三维空间里有 $n$ 条直线,请找出一个直线的集合,使得这个集合里的直线两两有交点。请告诉他这个集合的最大大小。JPY 又瞬间秒掉了这道题，现在他想来考考你，来确认自己是否能真的虐场。

请计算 $C[k]=\sum(a[i]*b[i-k])$ 其中 $k \leq i < n$ ，并且有 $n \leq 10 ^ 5$。 $a,b$ 中的元素均为小于等于 $100$ 的非负整数。

链接

bzoj2194

输入

第一行一个整数 $N$ ,接下来 $N$ 行，第 $i+2 \cdots i+N-1$ 行，每行两个数，依次表示$a[i],b[i]$ $(0 \leq i < N)$。

输出

输出 $N$ 行，每行一个整数，第 $i$ 行输出 $C[i-1]$。

给出两个 $n$ 位 $10$ 进制整数 $x$ 和 $y$，你需要计算 $x \times y$。

链接

bzoj2179

输入

第一行一个正整数 $n$。 第二行描述一个位数为 $n$ 的正整数 $x$。 第三行描述一个位数为 $n$ 的正整数 $y$。

输出

输出一行，即 $x \times y$ 的结果。