题目描述

        Vivek initially has an empty array a and some integer constant m.
        He performs the following algorithm:
        Select a random integer x uniformly in range from 1 to m and append it to the end of a.
        Compute the greatest common divisor of integers in a.

• In case it equals to 1, break
• Otherwise, return to step 1.

        Find the expected length of a. It can be shown that it can be represented as $\frac {P}{Q}$ where $P$ and $Q$ are coprime integers and $Q≠0(mod {10^9+7})$. Print the value of $ P⋅Q^{-1}(mod 10^9+7)$.

        本文谈一个数论方面的玄学算法。

        介绍一种可以在$O(\sqrt nlogn)$复杂度下求$n! mod P$的算法。阅读本文需要前缀知识：任意模数NTT以及拉格朗日插值法。

难度：NOI/NOI+/CTSC

题目描述

        在很久很久以前，有一棵n个点的树，每个点有一个点权。
        现在有q次操作，每次操作是修改一个点的点权或指定一个点，询问以这个点为根时每棵子树点权和的平方和。

难度：NOI/NOI+/CTSC

题目描述

        方伯伯正在做他的Oj。现在他在处理Oj上的用户排名问题。Oj上注册了n个用户，编号为1～n“，一开始他们按照编号排名。
        方伯伯会按照心情对这些用户做以下四种操作，修改用户的排名和编号：

• 操作格式为1 x y，意味着将编号为x的用户编号改为y，而排名不变，执行完该操作后需要输出该用户在队列中的位置，数据保证x必然出现在队列中，同时，1是一个当前不在排名中的编号。
• 操作格式为2 x，意味着将编号为x的用户的排名提升到第一位，执行完该操作后需要输出执行该操作前编号为x用户的排名。
• 操作格式为3 x，意味着将编号为x的用户的排名降到最后一位，执行完该操作后需要输出执行该操作前编号为x用户的排名。
• 操作格式为4 k，意味着查询当前排名为k的用户编号，执行完该操作后需要输出当前操作用户的编号。

        但同时为了防止别人监听自己的工作，方伯伯对他的操作进行了加密，即将四种操作的格式分别改为了：

• x+a y+a
• x+a
• x+a
• k+a

        其中a为上一次操作得到的输出，一开始a=0。
        例如：上一次操作得到的输出是5这一次操作的输入为：1 13 15因为这个输入是经过加密后的，所以你应该处理的操作是1 8 10现在你截获了方伯伯的所有操作，希望你能给出结果。

        记这个题主要是弥补一下数据结构优化DP的相关知识。题目来源：2019多校赛第三场D题。

        超好的一道支配树题目。来源：2019多校赛第三场B题。

难度：省选/NOI-

题目描述

        S国有N个城市，编号从1到N。城市间用N-1条双向道路连接，满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。
        为了方便，我们用不同的正整数代表各种宗教， S国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国政府为每个城市标定了不同的旅行评级，旅行者们常会记下途中（包括起点和终点）留宿过的城市的评级总和或最大值。
        在S国的历史上常会发生以下几种事件：

• “CC x c“：城市x的居民全体改信了c教；
• “CW x w“：城市x的评级调整为w;
• “QS x y“：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级总和；
• “QM x y“：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级最大值。

        由于年代久远，旅行者记下的数字已经遗失了，但记录开始之前每座城市的信仰与评级，还有事件记录本身是完好的。请根据这些信息，还原旅行者记下的数字。 为了方便，我们认为事件之间的间隔足够长，以致在任意一次旅行中，所有城市的评级和信仰保持不变。

难度：省选/NOI-

题目描述

        小Z有一片森林，含有N个节点，每个节点上都有一个非负整数作为权值。初始的时候，森林中有M条边。
        小Z希望执行T个操作，操作有两类：

• Q x y k查询点x到点y路径上所有的权值中，第k小的权值是多少。此操作保证点x和点y连通，同时这两个节点的路径上至少有k个点。
• L x y在点x和点y之间连接一条边。保证完成此操作后，仍然是一片森林。

        为了体现程序的在线性，我们把输入数据进行了加密。设lastans为程序上一次输出的结果，初始的时候lastans为0。
        对于一个输入的操作Q x y k,其真实操作为Q x^lastans y^lastans k^lastans。
        对于一个输入的操作L x y，其真实操作为L x^lastans y^lastans。其中^运算符表示异或，等价于pascal中的xor运算符。
        请写一个程序來帮助小Z完成这些操作。
        对于所有的数据，$n,m,T<=8*10^4$

难度：省选/NOI-

题目描述

        有n个小朋友要进行比赛，他们要被分为若干队伍。每一个小朋友都有一个要求，其中第i个小朋友要求他所在的队伍最少要有$a_i$个人（包括自己）。
        现在请你求出一种划分方案，在满足所有小朋友的要求的情况下，最大化队伍的数量。同时在此基础上，请你最小化人数最多的队伍的人数。