NIRVANA

Problem

Roadside Trees

$\mathrm{Time\;limit:\;5\;Sec}$
$\mathrm{Memory\;limit:\;256\;MB}$

Description

Squirrel Liss loves nuts. Liss asks you to plant some nut trees.
There are $n$ positions (numbered 1 to $n$ from west to east) to plant a tree along a street. Trees grow one meter per month. At the beginning of each month you should process one query. The query is one of the following types:

• Plant a tree of height $h$ at position $p$.
• Cut down the $x^{th}$ existent (not cut) tree from the west (where $x$ is 1-indexed). When we cut the tree it drops down and takes all the available place at the position where it has stood. So no tree can be planted at this position anymore.

After processing each query, you should print the length of the longest increasing subsequence. A subset of existent trees is called an increasing subsequence if the height of the trees in the set is strictly increasing from west to east (for example, the westmost tree in the set must be the shortest in the set). The length of the increasing subsequence is the number of trees in it.
Note that Liss don’t like the trees with the same heights, so it is guaranteed that at any time no two trees have the exactly same heights.

Input

The first line contains two integers: $n$ and $m$ $(1\le n\le 10^5; 1\le m\le 2\cdot 10^5)$ – the number of positions and the number of queries.
Next $m$ lines contains the information of queries by following formats:

• If the $i^{th}$ query is type 1, the $i^{th}$ line contains three integers: 1, $p_i$, and $h_i$ $(1\le p_i\le n,1\le h_i\le 10)$, where $p_i$ is the position of the new tree and $h_i$ is the initial height of the new tree.
• If the $i^{th}$ query is type 2, the $i^{th}$ line contains two integers: 2 and $x_i$ $(1\le x_i\le 10)$, where the $x_i$ is the index of the tree we want to cut.
  The input is guaranteed to be correct, i.e.,
• For type 1 queries, $p_i$ will be pairwise distinct.
• For type 2 queries, $x_i$ will be less than or equal to the current number of trees.
• At any time no two trees have the exactly same heights.

In each line integers are separated by single spaces.

Output

Print $m$ integers – the length of the longest increasing subsequence after each query. Separate the numbers by whitespaces.

Problem

【SHOI2017】分手是祝愿

$\mathrm{Time\;Limit:\;20\;Sec}$
$\mathrm{Memory\;Limit:\;512\;MB}$

Description

Zeit und Raum trennen dich und mich.
时空将你我分开。$\mathrm{B 君}$在玩一个游戏，这个游戏由 $n$ 个灯和 $n$ 个开关组成，给定这 $n$ 个灯的初始状态，下标为从 $1$ 到 $n$ 的正整数。每个灯有两个状态亮和灭，我们用 $1$ 来表示这个灯是亮的，用 $0$ 表示这个灯是灭的，游戏的目标是使所有灯都灭掉。但是当操作第 $i$ 个开关时，所有编号为 $i$ 的约数（包括 $1$ 和 $i$）的灯的状态都会被改变，即从亮变成灭，或者是从灭变成亮。$\mathrm{B 君}$发现这个游戏很难，于是想到了这样的一个策略，每次等概率随机操作一个开关，直到所有灯都灭掉。这个策略需要的操作次数很多， $\mathrm{B 君}$想到这样的一个优化。如果当前局面，可以通过操作小于等于 $k$ 个开关使所有灯都灭掉，那么他将不再随机，直接选择操作次数最小的操作方法（这个策略显然小于等于 $k$ 步）操作这些开关。$\mathrm{B 君}$想知道按照这个策略（也就是先随机操作，最后小于等于 $k$ 步，使用操作次数最小的操作方法）的操作次数的期望。这个期望可能很大，但是 $\mathrm{B 君}$发现这个期望乘以 $n!$ 一定是整数，所以他只需要知道这个整数对 $100003$ 取模之后的结果。

Input

第一行两个整数 $n$, $k$。
接下来一行 $n$ 个整数，每个整数是 $0$ 或者 $1$，其中第 $i$ 个整数表示第 $i$ 个灯的初始情况。
$1\le n\le 100000$, $0\le k\le n$

Output

一行，为操作次数的期望乘以 $n!$ 对 $100003$ 取模之后的结果。

Problem

【NOI2005】聪聪和可可

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;162\;MB}$

Description

Input

第一行为两个整数$N$和$E$，以空格分隔，分别表示森林中的景点数和连接相邻景点的路的条数。
第二行包含两个整数$C$和$M$，以空格分隔，分别表示初始时聪聪和可可所在的景点的编号。
接下来$E$行，每行两个整数，第$i+2$行的两个整数$A_i$和$B_i$表示景点$A_i$和景点$B_i$之间有一条无向边。
输入保证任何两个景点之间不会有多于一条路直接相连，且聪聪和可可之间必有路直接或间接的相连。

Output

输出一个实数，四舍五入保留三位小数，表示平均多少个时间单位后聪聪会把可可吃掉。

Problem

【SHOI2014】概率充电器

$\mathrm{Time\;Limit:\;40\;Sec}$
$\mathrm{Memory\;Limit:\;256\;MB}$

Description

著名的电子产品品牌$\mathrm{SHOI}$刚刚发布了引领世界潮流的下一代电子产品——概率充电器：
“采用全新纳米级加工技术，实现元件与导线能否通电完全由真随机数决定！$\mathrm{SHOI}$概率充电器,您生活不可或缺的必需品！能充上电吗？现在就试试看吧！”
$\mathrm{SHOI}$概率充电器由$n-1$条导线连通了$n$个充电元件。进行充电时，每条导线是否可以导电以概率决定，每一个充电元件自身是否直接进行充电也由概率决定。
随后电能可以从直接充电的元件经过通电的导线使得其他充电元件进行间接充电。
作为$\mathrm{SHOI}$公司的忠实客户，你无法抑制自己购买$\mathrm{SHOI}$产品的冲动。在排了一个星期的长队之后终于入手了最新型号的$\mathrm{SHOI}$概率充电器。
你迫不及待地将$\mathrm{SHOI}$概率充电器插入电源——这时你突然想知道，进入充电状态的元件个数的期望是多少呢？

Input

第一行一个整数$n$表示概率充电器的充电元件个数，充电元件由$1\sim n$编号。
之后的$n-1$行每行三个整数$a, b, p$，描述了一根导线连接了编号为$a$和$b$的充电元件，通电概率为$p\%$。
第$n+2$行$n$个整数$q_i$。表示$i$号元件直接充电的概率为$q_i\%$。

Output

输出一行一个实数，为进入充电状态的元件个数的期望，四舍五入到六位小数。

Problem

【CERC2017】Gambling Guide

$\mathrm{Time\;Limit:\;20\;Sec}$
$\mathrm{Memory\;Limit:\;512\;MB}$
$\mathrm{Special\;Judge}$

Description

给定一张$n$个点，$m$条双向边的无向图。
你要从$1$号点走到$n$号点。当你位于$x$点时，你需要花$1$元钱，等概率随机地买到与$x$相邻的一个点的票，只有通过票才能走到其它点。
每当完成一次交易时，你可以选择直接使用那张票，也可以选择扔掉那张票然后再花$1$元钱随机买另一张票。注意你可以无限次扔票。
请使用最佳的策略，使得期望花的钱数最少。

Input

第一行包含两个正整数$n,m$ $(1\le n,m\le3\times10^5)$，表示点数和边数。
接下来$m$行，每行两个正整数$u,v$ $(1\le u,v\le n)$，表示一条双向边。
输入数据保证无重边、无自环，且$1$号点一定可以走到$n$号点。

Output

输出一行一个实数，即最少的期望花费，当绝对或者相对误差不超过$10^{-6}$时视为正确。

Problem

彩色圆环

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;259\;MB}$

Description

Input

仅有一行，该行给出依次两个正整数$N,M$，分别表示宝石的个数和宝石在变化时可能变成的颜色种类数。

Output

应仅有一行，该行给出一个实数$E(R)$，表示圆环的“美观程度”的期望值。

Problem

Green Hackenbush

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

有一个古老的游戏叫做$\mathrm{Green\;Hackenbush}$，游戏是这样进行的：两个人轮流在一棵树上删边，每次删边后不与根联通的子树直接被忽略，不能删边的游戏者输。$\mathrm{Alice}$和$\mathrm{Bob}$也在玩这个游戏，不过他们面对的是$n$棵树，第$i$棵树是含有$a_i$个节点的二叉树。先手的$\mathrm{Alice}$想知道自己有多大的概率获胜(假设我们的$\mathrm{Alice}$和$\mathrm{Bob}$同学都是无限聪明的)。

Input

第一行一个数$n$。
接下来每行一个数$a_i$。

Output

一个保留$6$位小数的实数$ans$。

Problem

Alice in linear land

$\mathrm{Time\;limit:\;2\;Sec}$
$\mathrm{Memory\;limit:\;256\;MB}$

Statement

Alice lives on a line. Today, she will travel to some place in a mysterious vehicle. Initially, the distance between Alice and her destination is $D$. When she input a number $x$ to the vehicle, it will travel in the direction of the destination by a distance of $x$ if this move would shorten the distance between the vehicle and the destination, and it will stay at its position otherwise. Note that the vehicle may go past the destination when the distance between the vehicle and the destination is less than $x$.
Alice made a list of $N$ numbers. The $i^{th}$ number in this list is $d_i$. She will insert these numbers to the vehicle one by one.
However, a mischievous witch appeared. She is thinking of rewriting one number in the list so that Alice will not reach the destination after $N$ moves.
She has $Q$ plans to do this, as follows:
Rewrite only the $q_i^{th}$ number in the list with some integer so that Alice will not reach the destination.
Write a program to determine whether each plan is feasible.

Constraints

$1\le N\le5\times10^5$
$1\le Q\le5\times10^5$
$1\le D\le10^9$
$1\le d_i\le10^9\;(1\le i\le N)$
$1\le q_i\le N\;(1\le i\le Q)$
$D$ and each $d_i$ are integers.

Input

Input is given from Standard Input in the following format:
$N\;D$
$d_1\;d_2\;\cdots\;d_N$
$Q$
$q_1\;q_2\;\cdots\;q_Q$

Output

Print $Q$ lines. The $i^{th}$ line should contain YES if the $i^{th}$ plan is feasible, and NO otherwise.

Problem

Ball Eat Chameleons

$\mathrm{Time\;limit:\;2\;Sec}$
$\mathrm{Memory\;limit:\;256\;MB}$

Statement

In Republic of AtCoder, Snuke Chameleons (Family: Chamaeleonidae, Genus: Bartaberia) are very popular pets. Ringo keeps $N$ Snuke Chameleons in a cage.
A Snuke Chameleon that has not eaten anything is blue. It changes its color according to the following rules:

• A Snuke Chameleon that is blue will change its color to red when the number of red balls it has eaten becomes strictly larger than the number of blue balls it has eaten.
• A Snuke Chameleon that is red will change its color to blue when the number of blue balls it has eaten becomes strictly larger than the number of red balls it has eaten.

Initially, every Snuke Chameleon had not eaten anything. Ringo fed them by repeating the following process K times:

• Grab either a red ball or a blue ball.
• Throw that ball into the cage. Then, one of the chameleons eats it.

After Ringo threw in $K$ balls, all the chameleons were red. We are interested in the possible ways Ringo could have thrown in $K$ balls. How many such ways are there? Find the count modulo $998244353$. Here, two ways to throw in balls are considered different when there exists $i$ such that the color of the ball that are thrown in the $i^{th}$ throw is different.

Constraints

$1\le N,K\le5\times10^5$
$N$ and $K$ are integers.

Input

Input is given from Standard Input in the following format:
$N\;K$

Output

Print the possible ways Ringo could have thrown in $K$ balls, modulo $998244353$.

Problem

Cowmpany Cowmpensation

$\mathrm{Time\;Limit:\;2\;seconds}$
$\mathrm{Memory\;Limit:\;256\;megabytes}$

Description

Allen, having graduated from the MOO Institute of Techcowlogy (MIT), has started a startup! Allen is the president of his startup. He also hires $n-1$ other employees, each of which is assigned a direct superior. If $u$ is a superior of $v$ and $v$ is a superior of $w$ then also $u$ is a superior of $w$. Additionally, there are no $u$ and $v$ such that $u$ is the superior of $v$ and $v$ is the superior of $u$. Allen himself has no superior. Allen is employee number $1$, and the others are employee numbers $2$ through $n$.
Finally, Allen must assign salaries to each employee in the company including himself. Due to budget constraints, each employee’s salary is an integer between $1$ and $D$. Additionally, no employee can make strictly more than his superior.
Help Allen find the number of ways to assign salaries. As this number may be large, output it modulo $10^9+7$.

Input

The first line of the input contains two integers $n$ and $D$ ($1\le n\le3000$, $1\le D\le10^9$).
The remaining $n-1$ lines each contain a single positive integer, where the $i^{th}$ line contains the integer $p_i$ ($1\le p_i\le i$). $p_i$ denotes the direct superior of employee $i+1$.

Output

Output a single integer: the number of ways to assign salaries modulo $10^9+7$.