宜昌网站模板,国外代理ip地址和端口,山西网站备案,深圳也放开了第五届信大超越杯团体赛部分题解
B 时间的礼物
题目大意#xff1a;
给定一个数n#xff0c;通过分解n得到一个m大小的数组#xff08;数组元素可以是0#xff09;。问一共有多少种解决方案。答案对P取模。
输入三个整数 n,m,P。
样例输入#xff1a; 4 2 10 样例输出…第五届信大超越杯团体赛部分题解
B 时间的礼物
题目大意
给定一个数n通过分解n得到一个m大小的数组数组元素可以是0。问一共有多少种解决方案。答案对P取模。
输入三个整数 n,m,P。
样例输入 4 2 10 样例输出 5 题解
看完这道题首先想到的是组合数学中的隔板法给定的数n可以看作是n个小球排成一列任意两个小球之间以及左右两端共n1个位置都可以插入隔板。插入m-1个隔板就可以正好将这n个小球分为m份任意一份中小球的数量就作为这个元素的值。
不过需要注意的是每个位置都可以插入多个隔板所以答案并不是 C n 1 m − 1 C_{n1}^{m-1} Cn1m−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 ) ∑ i 0 i n f ( i , m − 1 ) f(n,m)\sum_{i0}^{in}f(i,m-1) f(n,m)∑i0inf(i,m−1)
由这个递推式自然而然地就可以想到杨辉三角因为杨辉三角有个性质就与其十分相似。
通过与杨辉三角进行对比得出结果式 f ( n , m ) C n m − 1 m − 1 f(n,m)C_{nm-1}^{m-1} f(n,m)Cnm−1m−1
问题的难点在于怎么求解 C n m − 1 m − 1 C_{nm-1}^{m-1} Cnm−1m−1用传统的递推方式复杂度太高对于n10^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为根的子树中所有节点价值增加 x2 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,∞上任意一点的前缀和都没有发生变化。
不过问题的难点在于题目给的时间范围是 t10^9求前缀和的话会超时。
不过人数的范围在 n10^6所以很显然需要对时间点进行离散化。
我们直接使用STL中的数据结构mapint,int来实现即可具体的实现方式见代码。
