Tsawke 的十二月模拟赛

注意事项

1. 所有文件名均保证为小写（友情提示：请格外注意文件名）。
2. C++ 中 main() 函数返回值必须为 int 且为 $0$$0$。
3. C++ 编译器开启 C++14 标准及 O2 优化。
4. 提交的程序源文件需独立文件夹。
5. 结果比较方式为全文比较（忽略行末空格及行尾回车）。
6. 程序可使用的栈空间限制与对应题目内存限制一致。
7. 评测采用机器配置为：11th Gen Intel(R) Core(TM) i5-11320H @ 3.20GHz。注意：测评将在 Linux 虚拟机中进行，配置会有部分降低，对于造成影响的题目会增加部分时限。
8. 编译选项为：g++ -o sample sample.cpp -lm -Wl,--stack=2147483647 -std=c++14 -O2。
9. 对于本地 Linux 环境下调试时，可以添加编译选项：-fsanitize=undefined,signed-integer-overflow,address 以检测未定义行为、整数溢出，地址越界等问题。
10. 对于提答题请将 .out 为扩展名的文件统一放到子目录下。

Tips

tsawke 对你们的期望得分为 $\ge 245$$\ge 245$。

同时部分数据尽量去卡了，可能卡的不是很好，故不保证一定会卡掉错误做法。

God does not play dice with the universe（lets_play_dice）

题目背景

既然放在了 T1 的位置，那么这道题自然是一道签到题了。

当然为了降低神仙题的难度，关键定理已在提示中给出。

题目背景之二

上帝可能不掷骰子，但是 tsawke 喜欢掷骰子。

题目描述

现在 tsawke 将会给你一个 $m$$m$ 面的骰子，其 $m$$m$ 面上标注了 $0,1,2,\cdots ,m-1$$0, 1, 2, \cdots, m - 1$ 共 $m$$m$ 个数字，每次丢出该骰子，显然会等概率生成一个 $[0,m-1]$$[0, m - 1]$ 的数字，具体地，如果我们认为骰子显示的数为 $X$$X$，那么离散型随机变量 $X$$X$ 的分布列为：

初次之外，tsawke 还为你提供了两个额外性质：

• $X$$X$ 的一阶原点矩（期望）为 $E(X)=\sum _{i=0}^{m-1}i\times P(X=i)={\displaystyle \frac{m-1}{2}}$$E(X) = \sum_{i = 0}^{m - 1}i \times P(X = i) = \dfrac{m - 1}{2}$。
• $X$$X$ 的二阶中心矩（方差）为 $D(X)=E((X-E(X){)}^2)=\sum _{i=0}^{m-1}(i-E(X){)}^2\times P(X=i)={\displaystyle \frac{m^2-1}{12}}$$D(X) = E((X - E(X))^2) = \sum_{i = 0}^{m - 1}(i - E(X))^2 \times P(X = i) = \dfrac{m^2 - 1}{12}$。

现在 tsawke 会分别丢 $n$$n$ 次该骰子，记第 $i$$i$ 次骰子显示的数为 $X_i$$X_i$，tsawke 会进行 $10$$10$ 次独立询问，分别给定 $A,B$$A, B$，求 $\sum _{i=1}^n{X}_i\in [A,B]$$\sum_{i = 1}^n X_i \in [A, B]$ 的概率。

存在多组数据。

输入格式

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

对于每组测试数据：

第一行两个整数 $m,n$$m, n$。

接下来 $10$$10$ 行每行两个整数 $A,B$$A, B$。

输出格式

对于每组数据，输出 $10$$10$ 行，每行输出一个实数表示对应询问的答案，要求绝对误差不超过 $1e-2$$1e-2$。

数据范围

对于 $100\mathrm{\%}$$100\%$ 的数据，保证 $T\le 10,2\le m\le 20,1\le n\le 2\times {10}^5,0\le A\le B\le (m-1)n$$T \le 10, 2 \le m \le 20, 1 \le n \le 2 \times 10^5, 0 \le A \le B \le (m - 1)n$。保证 $n>800$$n \gt 800$ 的数据不超过 $2$$2$ 组。

对于具体的数据范围与约定：

Examples

Input_1

xxxxxxxxxx
12
1
1
2
2 19
3
0 0
4
0 1
5
0 2
6
0 3
7
0 4
8
0 5
9
0 6
10
0 7
11
0 8
12
0 9

Output_1

xxxxxxxxxx
10
1
0.000002
2
0.000038
3
0.000364
4
0.002213
5
0.009605
6
0.031784
7
0.083534
8
0.179642
9
0.323803
10
0.500000

Examples_2

见下发文件中 /lets_play_dice/*。

提示

tsawke 觉得这道题有一些用到的性质似乎比较冷门，所以作为一个良心出题人，tsawke 为你们提供了几个可能用得到的定理。

对于期望为 $\mu$$\mu$，方差为 ${\sigma }^2$$\sigma^2$ 的正态分布 $N(\mu ,{\sigma }^2)$$N(\mu, \sigma^2)$，其概率密度函数为：

对于 $n$$n$ 个独立同分布的随机变量 $X_1,X_2,\cdots ,X_n$$X_1, X_2, \cdots, X_n$，若 $E(X_i)=\mu ,D(X_i)={\sigma }^2$$E(X_i) = \mu, D(X_i) = \sigma^2$，令：

若 $n$$n$ 足够大，则我们认为 $Y_n\sim N(0,1)$$Y_n \sim N(0, 1)$。

真正的OIer从不女装（dress_up）

题目背景

众所周知，女装只有零次和无数次。

题目描述

给定序列 $a_n$$a_n$。

存在如下定义：若一个序列中所有数字均相同，那么我们称该序列为 "tsawke序列"。

对于每次的询问会给定 $l,r$$l, r$，求序列 $a_n$$a_n$ 中左右端点都在 $[l,r]$$[l, r]$ 中的最长的 "tsawke序列" 的长度。

直接这么问就太单调了，所以 tsawke 决定进行操作——“女装”，定义每次女装操作可以在询问区间 $[l,r]$$[l, r]$ 中任意挑选一个位置 $p$$p$，然后分别翻转区间 $[l,p]$$[l, p]$ 和 $(p,r]$$(p, r]$。

给定 $m$$m$ 个操作，有如下两种格式：

R l r x：将序列中 $[l,r]$$[l, r]$ 区间推平为 $x$$x$。

Q l r k：独立查询在区间 $[l,r]$$[l, r]$ 中进行最多 $k$$k$ 次女装操作（可以不做或做少于 $k$$k$ 次）后可能得到的最长 "tsawke序列" 长度。

Tips：再次提醒，询问独立。

输入格式

第一行两个整数 $n,m$$n, m$。

第二行 $n$$n$ 个整数表示序列 $a_n$$a_n$。

接下来 $m$$m$ 行按照格式给定操作。

输出格式

对于每次 $Q$$Q$ 操作，输出对应的答案。

数据范围

对于 $20\mathrm{\%}$$20\%$ 的数据，满足 $1\le n,m\le 100$$1 \le n, m \le 100$。

对于另外 $10\mathrm{\%}$$10\%$ 的数据，保证所有询问中 $k=0$$k = 0$。

对于另外 $10\mathrm{\%}$$10\%$ 的数据，不存在 $R$$R$ 操作。

对于 $100\mathrm{\%}$$100\%$ 的数据，满足 $1\le n,m\le 2\times {10}^5,0\le k\le {10}^3,1\le a_i,x\le {10}^9,1\le l\le r\le n$$1 \le n, m \le 2 \times 10^5, 0 \le k \le 10^3, 1 \le a_i, x \le 10^9, 1 \le l \le r \le n$。

特别地，对于后 $80\mathrm{\%}$$80\%$ 的数据，保证数据不随机。

Examples

Input_1

xxxxxxxxxx
6
1
10 4
2
3 3 3 3 2 3 3 3 2 2
3
Q 1 6 1
4
Q 1 6 0
5
R 8 8 2
6
Q 5 10 1

Output_1

xxxxxxxxxx
3
1
5
2
4
3
4

Examples_2

见下发文件中 /dress_up/*。

提示

对于样例的说明：

对于第一次询问，询问的区间为：

3 3 3 3 2 3

女装1次，将区间$[1,4]$$[1,4]$和$[5,6]$$[5,6]$分别翻转,得到：

3 3 3 3 3 2

此时可得到最长 “tsawke序列”，长度为5。可以证明没有别的女装方法能得到更长的 “tsawke序列”。

此后询问以此类推。

同时提供读入优化模板：

xxxxxxxxxx
15
1
template < typename T = int >
2
inline T read(void){
3
    T ret(0);
4
    int flag(1);
5
    char c = getchar();
6
    while(c != '-' && !isdigit(c))c = getchar();
7
    if(c == '-')flag = -1, c = getchar();
8
    while(isdigit(c)){
9
        ret *= 10;
10
        ret += int(c - '0');
11
        c = getchar();
12
    }
13
    ret *= flag;
14
    return ret;
15
}

简单数据结构（dote___strvct）

题目背景

这道题需要抓紧时间嗷！

题目描述

给定序列 $a_n$$a_n$，及 $m$$m$ 个操作，以以下格式给出：

• 1 l r：输出 $(\sum _{i=l}^r{a}_i)mod1e9+7$$(\sum_{i = l}^r a_i) \bmod{1e9 + 7}$。
• 2 l r v：区间推平 $[l,r]$$[l, r]$ 为 $v$$v$。
• 3 l r v：对区间 $[l,r]$$[l, r]$ 加 $v$$v$。
• 4 l1 r1 l2 r2：将 $[l_1,r_1]$$[l_1, r_1]$ 的序列复制并覆盖到 $[l_2,r_2]$$[l_2, r_2]$。
• 5 l1 r1 l2 r2：将 $[l_1,r_1]$$[l_1, r_1]$ 的序列与 $[l_2,r_2]$$[l_2, r_2]$ 的序列交换。
• 6 l r：翻转区间 $[l,r]$$[l, r]$ 的序列。

输入格式

第一行两个整数 $n,m$$n, m$。

第二行 $n$$n$ 个整数表示序列 $a_n$$a_n$。

接着 $m$$m$ 行描述 $m$$m$ 个操作。

输出格式

对于每个操作 $1$$1$ 输出一行一个答案。

最后一行输出操作后的序列 $a_n$$a_n$。

数据范围

对于 $10\mathrm{\%}$$10\%$ 的数据，满足 $n,m\le {10}^3$$n, m \le 10^3$。

对于 $20\mathrm{\%}$$20\%$ 的数据，满足 $n,m\le 5\times {10}^4$$n, m \le 5 \times 10^4$。

对于 $30\mathrm{\%}$$30\%$ 的数据，满足 $n,m\le 1.5\times {10}^5$$n, m \le 1.5 \times 10^5$。

对于另外 $20\mathrm{\%}$$20\%$ 的数据，满足不存在操作 $4$$4$。

对于 $100\mathrm{\%}$$100\%$ 的数据，满足 $n,m\le 3\times {10}^5,0\le a_i,v\le {10}^9+7$$n, m \le 3 \times 10^5, 0 \le a_i, v \le 10^9 + 7$，且数据完全随机。

对于复制和交换操作，保证两区间长度相同且无交。

Examples

Input_1

xxxxxxxxxx
12
1
10 10
2
7 1 3 2 2 4 0 1 2 2 
3
4 10 10 3 3
4
3 4 10 5
5
6 6 7
6
6 9 10
7
1 10 10
8
5 9 10 6 7
9
2 8 10 0
10
5 4 4 5 5
11
5 2 4 8 10
12
3 3 9 0

Output_1

xxxxxxxxxx
2
1
7
2
7 0 0 0 7 7 7 1 2 7

Examples_2

见下发文件中 /dote___strvct/*。

提示

本题方法不局限于一种。

什么？？？NP问题？？？（np_graph_isomorphism）

题目背景

首先先放一段原题中对于 NP 和 NPC 等问题的叙述。

当学生们遇到某个难题时经常会说“这怎么做，这不是 NP 问题吗？”、“这个只有搜了，这己经被证明是 NP 问题了”。但是，你应该淸楚，大多数人此时所说的NP问题其实都是指 NPC 问题。很多人没有真正掌握 NP 问题和 NPC 问题这两个基本概念。其实 NP 问题并不是那种“只有搜才行”的问题，NPC 问题才是。

很久以前就有一个古老的传说：有―个著名的问题，即P是否等于NP的问题，传说中谁要是证明或者证伪了这个命题，他将获得幸福。这里P是指能在多项式时间里求解的问题的集合。而NP是指可在多项式时间里验证的问题的集合。显然P是NP的子集，因为能在多项式时间里求解的问题，必定可在多项式时间里验证。

到目前为止还没有人因这个命题得到幸福。但是，有一个总的趋势，也就是人们普遍认为，$P=NP$$P=NP$ 不成立，即，多数人相信，至少存在一个不可能有多项式时间复杂度的求解算法的NP问题。人们如此坚信 $P\ne NP$$P \neq NP$ 是有原因的，因为在研究NP问题的过程中找出了一类非常特殊的NP问题叫做NP-完全问题，也就是所谓的NPC问题。正是因为存在NPC问题，才使人们相信 $P\ne NP$$P \neq NP$。

在提出NPC的概念之后，绝大多数“自然”的难题最后都被证明是NPC问题，只有三个例外，它们分别是：

• 线形规划问题；
• 图同构问题；
• 素数判定问题与大数分解问题。

题目背景之二

虽然图的同构显然是一个 NP 问题，但是 tsawke 还是希望你能够以更优越的复杂度帮他解决这个问题。

题目描述

首先给定一下图的同构的定义：若将 $A$$A$ 图的顶点经过重新标号后可以使得 $A$$A$ 图和 $B$$B$ 图的顶点集和边集一一对应，那么称 $A$$A$ 图和 $B$$B$ 图是同构的。

现在你获得了一个不大的整数 $n$$n$，对于所有的含有 $n$$n$ 个点的简单无向图，显然其最多有 $2^{(\genfrac{}{}{0ex}{}{n}{2})}$$2^{n \choose 2}$ 条边，你需要输出这些所有图中，有多少种本质不同图。

换句话说，同构的图算作一种，你需要计算有多少种不同的图。

答案对 $p$$p$ 取模，已知 $p$$p$ 为质数。

输入格式

一行两个非负整数 $n,p$$n, p$，表示图的顶点数和模数。

输出格式

一行一个整数，表示本质不同的图的数量，对 $p$$p$ 取模。

数据范围

对于 $20\mathrm{\%}$$20\%$ 的数据，满足 $1\le n\le 5$$1 \le n \le 5$。（这是给你们手画的部分分）

对于 $40\mathrm{\%}$$40\%$ 的数据，满足 $1\le n\le 10$$1 \le n \le 10$。（这部分分给的挺足了）

对于 $100\mathrm{\%}$$100\%$ 的数据，满足 $1\le n\le 60,p>n$$1 \le n \le 60, p \gt n$，且保证 $p$$p$ 为质数。

Examples

Input_1

xxxxxxxxxx
1
1
1 1145141

Output_1

xxxxxxxxxx
1
1
1

Input_2

xxxxxxxxxx
1
1
3 1145141

Output_2

xxxxxxxxxx
1
1
4

Examples_3

见下发文件中 /np_graph_isomorphism/*。