NIRVANA

Problem

【NOIP2018模拟1】数三角形

$\mathrm{Time\;Limit:\;1000\;ms}$
$\mathrm{Memory\;Limit:\;262144\;K}$

Description

图论中的三元环也称作三角形。在这个问题里，我们要在随机图里数三角形。

我们有一张完全图G，它的边有可能是红色或者蓝色，有三种可能的随机性：

1. 某条边 $e$ ，以 $p_e$ 的概率是红色，以 $1-p_e$ 的概率是蓝色；
2. 对于一组若干条边 $e_1, e_2, \cdots, e_k$，只有一条边是红色其他是蓝色，且 $e_i$ 是红色的概率为 $p_i$，满足 $\sum^{k}_{i=1}p_i=1$；
3. 对于一组若干条边 $e_1, e_2, \cdots, e_k$，只有一条边是蓝色其他是红色，且 $e_i$ 是红色的概率为 $p_i$，满足 $\sum^{k}_{i=1}p_i=1$。

你需要找出三条边同色的三角形的期望。

Input

第一行一个数 $n$, 表示G的顶点个数。接下来 $\frac{n(n - 1)}{2}$ 行，每行四或五个数字 $i,j,v,p,(l)$，表示点 $i$ 和 点 $j$ 之间的边的随机种类是 $v$ , 且它对应的概率为 $p$ 。满足 $i \neq j, v \in {1, 2, 3}$ 且 $p$ 是 $0$ 到 $1$ 的实数。保证每条边恰好出现一次。如果 $v > 1$，则还会有一个输入 $l$ ,表示这条边属于那一组。如前面所述，同一组的所有边的概率加起来为 $1$ ，且恰好有一条为红色$(v = 2)$或蓝色$(v = 3)$。保证每组至少有两条边，且组的编号为从 $1$ 开始的连续编号。

Output

一行，一个数，表示同色三角形的期望个数，保留两位小数。

Problem

【NOIP2017模拟3】数三角形

$\mathrm{Time\;Limit:\;3000\;ms}$
$\mathrm{Memory\;Limit:\;262144\;K}$

Description

刚刚上高中的洁洁在学习组合数学的过程中遇到一道麻烦的题目，她希望你能帮助她解决。给定一张无向完全图 $G$，其中大部分边被染成蓝色，但也有一些边被染成红色或者绿色。现在，洁洁需要给这张图的多样性进行打分。一张图的多样性取决于它的同色和异色三角形的个数。具体来说，$G$ 中每有一个三边颜色都互不同的三角形（异色三角形）可以得 $3$ 分，每有一个三边颜色都相同的三角形（同色三角形）则要被扣掉 $6$ 分，其它三角形不得分也不扣分。
现在，请你写一个程序来计算 $G$ 的多样性分数。

Input

第一行两个正整数 $n$ 和 $m$，其中 $n$ 表示 $G$ 中顶点的个数，$m$ 表示 $G$ 中红色或者绿色的边的条数。
接下来 $m$ 行每行包括三个整数 $a,b,c$，代表连接顶点 $a$ 和顶点 $b$ 的边颜色为红色 $(c=1)$ 或者绿色 $(c=2)$。

Output

一行，$G$ 的多样性得分。

Problem

【NOIP2017模拟2】银河战舰

$\mathrm{Time\;Limit:\;1000\;ms}$
$\mathrm{Memory\;Limit:\;262144\;K}$

Description

瑞奥和玛德利德是非常好的朋友。瑞奥平时的爱好是吹牛，玛德利德的爱好是戳穿瑞奥吹的牛。
这天瑞奥和玛德利德来到了宇宙空间站，瑞奥向玛德利德炫耀这个空间站里所有的银河战舰都是自己的。整个空间站可以看成一个无限大的二维平面，每个战舰都可以看做一个点，在空间站中一共分布着 $N$ 艘银河战舰。
玛德利德：“你说这些都是你的，那你让他们动一动啊”。
瑞奥：“诶你看,那艘动了！”。
玛德利德：“操作指令由我来发，一共有 $5$ 种动的方法…”。
瑞奥：“我觉得这样有失公正…”。

Input

第一行一个正整数 $N$，表示战舰的数量。
接下来 $N$ 行，每行两个实数，代表第 $i$ 个战舰的 $x,y$ 坐标。
然后一个正整数 $M$，代表调度的次数。
接下来 $M$ 行操作，每个操作都是如下类型的一种：

• $M,l,r,p,q$：把编号在 $[l,r]$ 区间内的战舰 $x$ 坐标加上 $p$，$y$ 坐标加上 $q$。
• $X,l,r$：把编号在 $[l,r]$ 区间内的战舰沿 $x$ 轴翻转。
• $Y,l,r$：把编号在 $[l,r]$ 区间内的战舰沿 $y$ 轴翻转。
• $O,l,r$：把编号在 $[l,r]$ 区间内的战舰沿直线 $y=x$ 翻转。
• $R,l,r,a$：把编号在 $[l,r]$ 区间内的战舰绕原点逆时针旋转 $a^\circ$。

Output

输出包括 $N$ 行，代表着 $N$ 艘战舰经过 $M$ 次调度之后的坐标（保留两位小数）。

Problem

【NOIP2017模拟3】任性的国王

$\mathrm{Time\;Limit:\;1000\;ms}$
$\mathrm{Memory\;Limit:\;262144\;K}$

Description

X 国的地图可以被看作一个两行 $n$ 列的网格状图。现在 X 国需要修建铁路，然而该国的国王非常小气，他只想保证位于某两列之间的所有城市互相可以到达就行了，在此基础上，他希望所花费的代价最小。
铁路可以建在任何两个相邻的点之间，使他们可以互相到达。可以作为工作人员，你已经整理出了为每一对相邻城市架设铁路所需要的花费。你需要准备好回答国王如下形式的问题。
对于 $(i,j)$：当前情况下，使第 $i$ 列到第 $j$ 列之间的所有城市连通的最小代价是多少（列下标从 $1$ 开始）？注意不能用其他列的城市。
然而你还有更大的困难，随着时间变化，使用某些边作为铁路的代价会发生改变，你必须有效率地处理这些变化。

Input

第一行两个正整数 $n,m$，表示该国有 $2$ 行 $n$ 列以及 $m$ 个询问或者操作。
第二行 $3n-2$ 个数，前 $n-1$ 个数依次表示在第一行的 $n-1$ 条边上修建铁路的代价。
接下来 $n−1$ 个数，依次表示在第二行的 $n-1$ 条边上修建铁路的代价。
最后 $n$ 个数，依次表示在第 $1$ 列到第 $n$ 列的边上修建铁路的代价。
接下来 $m$ 行的输入具有如下形式，$K,S,T$，其中

• 若 $K=1$，则表示询问当前状态下，使所有第 $S$ 列到第 $T$ 列之间的城市连通需要的最小代价。
• 若 $K=2$，则表示位于第 $1$ 行第 $S$ 列的点到第 $1$ 行第 $S+1$ 列的点之间的边上修建铁路的代价变为 $T$。
• 若 $K=3$，则表示位于第 $2$ 行第 $S$ 列的点和第 $2$ 行第 $S+1$ 列的点之间的边上修建铁路的代价变为 $T$。
• 若 $K=4$，则表示第 $S$ 列的边上修建铁路的代价变为 $T$。

Output

依次对每个询问，用一行输出相应的答案。

Problem

【NOIP2018模拟3】手拉手

$\mathrm{Time\;Limit:\;1000\;ms}$
$\mathrm{Memory\;Limit:\;131072\;K}$

Description

小 P 是个幼儿园老师。有一天，他组织 $n$ 个小朋友玩游戏。游戏开始时，每个小朋友伸出两只手，没有手相互拉在一起。每次，小 P 等概率随机挑选两只空着的手，让这两只手拉在一起。小 P 一直重复这个操作，直到所有的手都拉在一起。小 P 在成为幼儿园老师之前是个数学专业的博士。因此，他想知道，当所有的手都拉在一起之后，小朋友们拉成的圈个数的期望是多少？其中，我们规定，一个小朋友左手拉右手的情况也形成一个圈。
由于小 P 忙着和小朋友们玩游戏，他找到了聪明的你，希望你能帮他解决这个问题。

Input

输入数据仅一行，包含一个正整数 $n$ ，表示小朋友的数量。

Output

输出文件仅一行，包含一个实数，表示当所有的手都拉在一起之后，小朋友们拉成的圈个数的期望是多少。输出和标准答案的绝对误差不能超过 $10^{-9}$。

Problem

斐波那契的最小公倍数

$\mathrm{Time\;Limit:\;3\;Sec}$
$\mathrm{Memory\;Limit:\;131072\;KB}$

Description

斐波那契数列定义如下：

$$F(0) = 0\\ F(1) = 1\\ F(n) = F(n-1) + F(n-2)\\$$

给出$n$个正整数$a_1, a_2,\cdots a_n$，求对应的斐波那契数的最小公倍数，由于数字很大，输出模 $1000000007$的结果即可。
例如：$\lbrace1,3,6,9\rbrace$, 对应的斐波那契数为：$\lbrace1,2,8,34\rbrace$, 他们的最小公倍数为$136$。

Input

第$1$行$1$个数$N$，表示数字的数量。（$2\le N\le50000$）。
第$2$至$N+1$行每行$1$个数，对应$a_i$。（$1\le a_i\le1000000$)。

Output

输出$\mathrm{lcm}(F(a_1),F(a_2),\cdots,F(a_n))\bmod{1000000007}$的结果。

Problem

Lucas的数论

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

Description

去年的Lucas非常喜欢数论题，但是一年以后的Lucas却不那么喜欢了。
在整理以前的试题时，发现了这样一道题目“求$\sum{f(i)}$,其中$1\le i\le N$”，其中$f(i)$表示$i$的约数个数。他现在长大了，题目也变难了。
求如下表达式的值：

$$\sum_{i=1}^{n}\sum_{j=1}^{n}f(ij)$$

其中$f(ij)$表示$ij$的约数个数。
他发现答案有点大，只需要输出模$1000000007$的值。

Input

第一行一个整数$n$。

Output

一行一个整数$ans$，表示答案模$1000000007$的值。

Problem

太鼓达人

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

Description

七夕祭上，$\mathrm{Vani}$牵着$\mathrm{cl}$的手，在明亮的灯光和欢乐的气氛中愉快地穿行。这时，在前面忽然出现了一台太鼓达人机台，而在机台前坐着的是刚刚被精英队伍成员$\mathrm{XLk}$、$\mathrm{Poet}$_$\mathrm{shy}$和$\mathrm{lydrainbowcat}$拯救出来的的$\mathrm{applepi}$。看到两人对太鼓达人产生了兴趣，$\mathrm{applepi}$果断闪人，于是$\mathrm{cl}$拿起鼓棒准备挑战。然而即使是在普通难度下，$\mathrm{cl}$的路人本性也充分地暴露了出来。一曲终了，不但没有过关，就连鼓都不灵了。$\mathrm{Vani}$十分过意不去，决定帮助工作人员修鼓。
鼓的主要元件是$M$个围成一圈的传感器。每个传感器都有开和关两种工作状态，分别用$1$和$0$表示。显然，从不同的位置出发沿顺时针方向连续检查$K$个传感器可以得到$M$个长度为$K$的$01$串。$\mathrm{Vani}$知道这$M$个$01$串应该是互不相同的。而且鼓的设计很精密，$M$会取到可能的最大值。现在$\mathrm{Vani}$已经了解到了K的值，他希望你求出$M$的值，并给出字典序最小的传感器排布方案。

Input

一个整数$K$。

Output

一个整数$M$和一个二进制串，由一个空格分隔。表示可能的最大的$M$以及字典序最小的排布方案，字符$0$表示关，$1$表示开。你输出的串的第一个字和最后一个字是相邻的。

Problem

Sightseeing Plan

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

Statement

Joisino is planning on touring Takahashi Town. The town is divided into square sections by north-south and east-west lines. We will refer to the section that is the $x^{th}$ from the west and the $y^{th}$ from the north as $(x,y)$.
Joisino thinks that a touring plan is good if it satisfies the following conditions:
Let $(p,q)$ be the section where she starts the tour. Then, $X_1\le p\le X_2$ and $Y_1\le q\le Y_2$ hold.
Let $(s,t)$ be the section where she has lunch. Then, $X_3\le s\le X_4$ and $Y_3\le t\le Y_4$ hold.
Let $(u,v)$ be the section where she ends the tour. Then, $X_5\le u\le X_6$ and $Y_5\le v\le Y_6$ hold.
By repeatedly moving to the adjacent section (sharing a side), she travels from the starting section to the ending section in the shortest distance, passing the lunch section on the way.
Two touring plans are considered different if at least one of the following is different: the starting section, the lunch section, the ending section, and the sections that are visited on the way. Joisino would like to know how many different good touring plans there are. Find the number of the different good touring plans. Since it may be extremely large, find the count modulo $10^9+7$.

Constraints

$1\le X_1\le X_2<X_3\le X_4<X_5\le X_6\le 10^6$
$1\le Y_1\le Y_2<Y_3\le Y_4<Y_5\le Y_6\le 10^6$

Input

Input is given from Standard Input in the following format:

$$\begin{matrix} X_1&X_2&X_3&X_4&X_5&X_6\\ Y_1&Y_2&Y_3&Y_4&Y_5&Y_6\\ \end{matrix}$$

Output

Print the number of the different good touring plans, modulo $10^9+7$.

Problem

【ACM-ICPC 2018 南京赛区网络预赛】Set

$\mathrm{Time\;Limit:\;1500\;ms}$
$\mathrm{Memory\;Limit:\;524288\;K}$

Description

Shinku is very interested in the set. One day, she got $n$ sets, and the $i^{th}$ number $a_i$ is in the $i^{th}$ set. But she doesn’t think it is interesting enough, so she applies $m$ magic to these sets. There are three kinds of magic:

• $1\;u\;v$: If the $u^{th}$ and $v^{th}$ numbers are not in one set, then the Shinku’s magic will merge the set containing the $u^{th}$ number and the set containing the $v^{th}$ number.
• $2\;u$: Shinku’s magic adds $1$ to each number in the set containing the $u^{th}$ number.
• $3\;u\;k\;x$: Shinku can immediately know how many numbers $t$ in the set containing the $u^{th}$ number satisfy $t\equiv x (\bmod\ 2^k)$ $(0 \le k\le 30,0\le x<2^k)$.

But unfortunately, for some reason the type $3$ magic fails. So Shinku wants you to tell her the answer after every type $3$ magic.
Note that there can be multiple numbers with the same value in one set, that is, numbers with the same value will not disappear when merged.

Input

The first line contains two integers $n,m$ $(1 \le n,m \le 6 \times 10^5)$, the number of initial sets and the number of the magic.
The second line contains $n$ integers. The $i^{th}$ number $a_i$ $(0 \le a_i \le 10^9)$ is the number in the $i^{th}$ set initially.
The next $m$ lines describe the sequence of magic. The $i^{th}$ line describes the $i^{th}$ magic. Each magic is a magic as described above.

Output

For each type $3$ magic, output the answer you are asked to calculate.