第五届信大超越杯团体赛部分题解

第五届信大超越杯团体赛部分题解

B 时间的礼物

题目大意：

给定一个数n，通过分解n得到一个m大小的数组（数组元素可以是0）。问一共有多少种解决方案。答案对P取模。

输入三个整数 n,m,P。

样例输入：

4 2 10

样例输出：

5

题解：

看完这道题首先想到的是组合数学中的隔板法，给定的数n可以看作是n个小球排成一列，任意两个小球之间以及左右两端（共n+1个位置）都可以插入隔板。插入m-1个隔板就可以正好将这n个小球分为m份，任意一份中小球的数量就作为这个元素的值。

不过需要注意的是，每个位置都可以插入多个隔板，所以答案并不是 $C_{n+1}^{m-1}$。

我们用 f(n,m) 来表示答案，推导一般规律：

f(0,2)=1 f(1,2)=2 f(2,2)=3 f(3,2)=4 f(4,2)=5

f(0,3)=1 f(1,3)=3 f(2,3)=6 f(3,3)=10 f(4,3)=15

f(0,4)=1 f(1,4)=4 f(2,4)=10 f(3,4)=20 f(4,4)=35

可以发现：$f(n,m)={\sum }_{i=0}^{i=n}f(i,m-1)$

由这个递推式自然而然地就可以想到杨辉三角，因为杨辉三角有个性质就与其十分相似。

通过与杨辉三角进行对比，得出结果式：​$f(n,m)=C_{n+m-1}^{m-1}$

问题的难点在于怎么求解 $C_{n+m-1}^{m-1}$，用传统的递推方式复杂度太高，对于n<=10^6的数据量会超时。

用预处理阶乘和阶乘逆元的方法也存在问题，因为模数P不一定是素数，可能有逆元不存在的情况发生。

所以我们的求解算法是，对分子和分母进行素因子分解，然后用分子素因子的幂减去分母对应的素因子的幂，最后再使用快速幂计算结果即可。

那么如何对n!进行素因子分解？

有一个递归公式：令g(n,p)表示 n！中素因子p的幂

则有 g(n,p) = g(n/p,p)+n/p

所以我们先用线性筛算法把数据范围内所有的素数筛出来，然后枚举素数，使用g(n,p)求出其任意素因子的幂，再结合上面的思路即可得到最终答案。

‍

C 财政大臣

题目大意：

给一颗树，每个节点都有一个价值，再给出若干操作，求最终每个节点的价值。

操作有以下两种：

• 1 u x，以u为根的子树中所有节点价值增加 x
• 2 u x，以u为根的子树中所有节点价值减少 x

样例输入：

3 2

1 2

1 3

3 2 1

1 1 1

2 2 1

样例输出：

4 2 2

题解：

首先对这颗树求一个dfn序，得到以任意一个节点x为根的子树的区间：[dfn[x],tail[x]]

然后基于这个dfn序建立一颗线段树，问题就转化为了线段树的区间修改、单点查询问题。

只要写线段树的时候细心一点，注意线段树节点的空间开辟，就没什么问题了。

‍

D 实验室有多少人

题目大意：

给出n个人到实验室和离开实验室的时间，求出实验室人最多的时候有多少人。

输入样例：

4

1 2

2 5

3 5

4 5

输出样例：

3

题解：

最容易想到的思路就是维护一个差分序列，然后对每一天求一个前缀和，取最大值即为最终答案。

就比如，有一个人第L天来到实验室，第R天离开实验室，那我们就在L这个位置上+1，在R这个位置上-1，此时区间 [L,R) 上任意一点的前缀和增加了1，而区间 (0,L) 和 [R,+∞）上任意一点的前缀和都没有发生变化。

不过问题的难点在于题目给的时间范围是 t<=10^9，求前缀和的话会超时。

不过人数的范围在 n<=10^6，所以很显然需要对时间点进行离散化。

我们直接使用STL中的数据结构map<int,int>来实现即可，具体的实现方式见代码。