#牛客守护神# 看起来是个很可爱的人，那，祝我好运吧！

[1]组合 题目描述 给出组合数 C(n,m) 表示从 n 个元素中选出 m 个元素的方案数。例如 C(5,2)=10,C(4,2)=6。可是当 n,m 比较大的时候，C(n,m) 很大。于是 xiaobo 希望你输出C(n,m)modp 的值。 输入 输入数据第一行是一个正整数 T，表示数据组数； 接下来是 T 组数据，每组数据有 3 个正整数 n,m,p。 对于所有数据，T≤100，1≤m≤n≤109，m≤104，m<p<109，p 是素数。 输出 对于每组数据，输出一个正整数，表示 C(n,m)modp 的结果。 样例输入 2 5 2 3 5 2 61 样例输出 1 1...

[1]序列的第k个数 题目描述 BSNY 在学等差数列和等比数列，当已知前三项时，就可以知道是等差数列还是等比数列。现在给你序列的前三项，这个序列要么是等差序列，要么是等比序列，你能求出第 k 项的值吗。 如果第 k 项的值太大，对 200907 取模。 输入 第一行一个整数 T，表示有 T 组测试数据； 对于每组测试数据，输入前三项 a,b,c，然后输入 k。 对于全部数据，1<=T<=100,1<=a<=b<=c<=109,1<=k<=109 输出 对于每组数据输出第 k 项的值，对 200907 取模。 样例输入 2 1 2 3 5 1 2...

[1]青蛙的约会 题目描述 两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具***置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。 我们把这两只青蛙分别叫做青蛙 A 和青蛙 B ，并且规定纬度线上东经 0 度处为原点，由东往西为正方向...

以下是我今天解题的题解报告： [1]数列操作 题目描述 给定n个数列，规定有两种操作，一是修改某个元素，二是求子数列[A,B]的连续和。数列的元素个数最多10万个，询问操作最多10万次。 输入 第一行2个整数n,m（n表示输入n个数列，m表示有m个操作） 第二行输入n个数列。 接下来M行，每更好行有三个数k,a,b(k=0表示求子数列[a,b]的和，k=1表示第a个数列加b) 输出 输出若干行数字，表示每次K=0时对应输出一个子数列[a,b]的连续和。 样例输入 10 5 1 2 3 4 5 6 7 8 9 10 1 1 5 0 1 3 0 4 8 1 7 5 0 4 8 样例输出 11...

以下是我今天解题的题解报告： [1] 黑暗城堡 题目描述 你知道黑暗城堡有N个房间（1≤N≤1000），M条可以制造的双向通道，以及每一条通道的长度。 城堡是树形的并且满足以下条件：如果所有的通道都被修建，设D[i]为第i号房间与第一号房间的最短路径长度；而S[i]为实际修建的树形城堡中第i号房间与第1号房间的路径长度；要求对于所有整数i（1≤i≤N），有S[i]=D[i]成立。 你想知道有多少种；不同的城堡修建放啊。当然，你只需要输出答案对 231 – 1 取模之后的结果就行了。 输入 第一行有两个整数 N 和 M。 之后 M 行，每行三个整数 X，Y 和 L，表示可以修建 X 和 Y 之间...

以下是我今天解题的题解报告： [1] 哈希 题目描述 在数据结构中，我们学过哈希表。我们知道，哈希存储方法是一种根据关键码值(Key value)而直接进行访问的数据结构方法。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数H(key)，存放记录的数组叫做哈希表。 在哈希表的构造中，哈希函数的选取显得异常重要。比如，在存储一个班级所有学生的某一门学科成绩的时候（假设该班人数<100），每个学生的学号有10~12位，我们不可能开出这么大的数组来储存，由于每个学生的学号末2位均不相同，我们可以开一个大小为100的数组，假设一个同学的学号为09...

以下是我今天解题的题解报告： [1] 求解next数组 题目描述： 在求解KMP过程中，会先求解next数组，给定一个字符（长度不超过40），输出对应next数组 具体描述： 给定一个字符串t，如 abcdabc，把从第一个字符开始的t的子串称为t的前缀，如a,ab,abc,abcd… 给定一个字符串t，如 abcdabc，把从某一个字符开始到最后一个字符的t子串称为t的后缀，如c,bc,abc,dabc,cdabc… 求出t的子串对应的 前缀长度等于后缀长度 的值 及 next数组。 如 a ab abc abcd abcda abcdab abcdabc 0 0 0 0 1 2 3 前缀子...

以下是我今天解题的题解报告： [1]点的距离 题目描述 给定一棵有n个结点的树，Q个询问，每次询问点x到点y亮点之间的距离 输入 第一行一个n，表示有n个节。 接下来有n-1行，每行2个整数x，y表示x，y之间有一条连边。 然后一个整数Q，表示有Q次询问，接下来Q行每行2个整数x，y表示询问x到y的距离。 输出 输出Q行，每行表示每个询问的结果 样例输入 6 1 2 1 3 2 4 2 5 3 6 2 2 6 5 6 样例输出 3 4 思路: 这题就是一个模板题,由于n和m都是20000的数据范围(不知道具体范围,题里也没说,就随便蒙了一个)，无法暴力求解，而lca单次查询是logn效率，...

以下是我今天解题的题解报告： [1]区间求和 题目描述 给定一数列，规定有两种操作，一是修改某个元素，二是求区间的连续和。 输入 输入数据第一行包含两个正整数n,m(n<=100000,m<=500000),以下是m行， 输出 每行有三个正整数k,a,b(k=0或1, a,b<=n).k=0时表示将a处数字加上b,k=1时表示询问区间[a,b]内所有数的和。对于每个询问输出对应的答案。 样例输入 10 20 0 1 10 1 1 4 0 6 6 1 4 10 1 8 9 1 4 9 0 10 2 1 1 8 0 2 10 1 3 9 0 7 8 0 3 10 0 1 1 1 ...

以下是我今天解题的题解报告： [1]树的统计 题目描述 一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成 一些操作： I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 I II. QSUM u v: 询问从点u到点v的路径上的节点的权值和 注意：从点u到点v的路径上的节点包括u和v本身 输入 输入的第一行为一个整数n，表示节点的个数。接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有 一条边相连。接下来n行，每行一个整数，第i行的整数wi表示节点i的权值。...

以下是我今天解题的题解报告： [1] intervals(Poj1201) 题目描述 一个整数集合Z有n个区间，每个区间有3个值，ai，bi，ci代表，在区间[ai,bi]上至少有ci个整数属于集合Z，ci可以在区间内任意取不重复的点。 现在要满足所有区间的约束条件，问最少可选多少个点。 输入 第一行一个整数n，表示区间个数 以下n行描述区间，第i+1行，三个整数ai，bi，ci，由空格隔开，其中 0 <= ai <= bi <= 50000 且1 <= ci <= bi - ai+1. 输出 一行，输出满足要求序列的长度的最小值 样例输入 5 3 7 3 8 ...