【题解】求次方和
【题目描述】
求解 (2^0 + 2^1 + 2^2+ ... + 2^n) % 2333
【输入描述】
一行，一个整数n。
【输出描述】
一行，表达式的正确结果
【样例输入】
2
【样例输出】
7
【数论】同余定理与同余方程
【算法】前缀和与差分(3)二维数组前缀和
【题解】数字的选择
【题目描述】
有n个非负整数，请从这n个非负整数中，选出m个数，在不改变m个数的顺序的情况下，构成一个新数列，要求该数列的中相邻两个数的差值绝对值的和尽可能小。
请问，这个最小的差值绝对值的和是多少？
比如：有5个数是2 1 8 5 9，如果从中选3个数，不改变顺序的情况下，要求相邻2个数的差值绝对值的和最小，选数方法可以是：2 1 5，差值绝对值的和是|1-2|+|5-1|=5。
【输入描述】
第1行输入2个整数，分别是n和m。（2≤m≤n≤100）
第2行，有n个非负整数，数字之间用空格隔开。
【输出描述】
按题意输出最小的差值绝对值的和。（本题保证计算出来的结果，在int的范围内）
【样例输入】
5 3 2 1 8 5 9
【样例输出】
5
【题解】导弹拦截
【题目描述】
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹的枚数和导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，每个数据之间至少有一个空格），计算这套系统最多能拦截多少导弹。
【输入描述】
第1行有1个整数n，代表导弹的数量。（n<=1000）
第2行有n个整数，代表导弹的高度。（雷达给出的高度数据是不大于30000的正整数）
【输出描述】
第一行：最多能拦截的导弹数；
第二行：要拦截所有导弹最少要配备的系统数。
【样例输入】
8 389 207 155 300 299 170 158 65
【样例输出】
6
【题解】分糖果
【题目描述】
小A在生日这天收到了哥哥送来的一盒糖果，这盒糖果共有M个，小A要把这盒糖果放到N个盘子中（允许有盘子不放），请问，有多少种不同的放法？
请注意：数值相同，顺序不同，我们视为是相同的放法，比如，1 1 6，和1 6 1、6 1 1，我们视为是同一种放法。
【输入描述】
输入包含多组测试样例。每组输入的第一行是一个整数t，表示数据有多少组。（t<=10）
接下来t行，每行输入两个整数M和N，代表有糖果的数量和盘子的数量。
（M和N均≥0，且≤20）
【输出描述】
对于每对输入的M和N，输出有多少种放法。
【样例输入】
1 7 3
【样例输出】
8
【题解】跳格子
【题目描述】
地面上有一排长度为n的格子1-n，每个格子上都有一个数xi，开始时你在位置0，每次你可以向前跳1-2格，然后取走格子上的数，直到跳到位置n+1。取走的数的和就是你的得分，现在你想知道你可能的最大得分是多少。
【输入描述】
一行四个整数n,A,B,C(n≤100000,0≤A,B,C≤10000)，其中n表示格子的数量。x[i]由如下方式生成：
for (int i = 1; i <= n; i++){
int tmp = ((long long)A * i * i + B * i + C) % 20000;
x[i] = tmp - 10000;
}
【输出描述】
一行一个整数ans表示可能的最大得分。
【样例输入】
3 1 1 1
【样例输出】
-9993
【题解】前缀最大值
【题目描述】
求一个数列的所有前缀最大值之和。
即：给出长度为n的数列a[i],求出对于所有1<=i<=n，max(a[1],a[2],...,a[i])的和。
比如，有数列：666 304 692 188 596，前缀最大值为：666 666 692 692 692，和为3408。
对于每个位置的前缀最大值解释如下：对于第1个数666，只有一个数，一定最大；对于第2个数，求出前两个数的最大数，还是666；对于第3个数，求出前3个数的最大数是692……其余位置依次类推，最后求前缀最大值得和。
由于读入较大，数列由随机种子生成。
其中a[1]=x，a[i]=(379*a[i-1]+131)%997。
【输入描述】
一行两个正整数n,x，分别表示数列的长度和随机种子。(n<=100000,x<997)
【输出描述】
一行一个正整数表示该数列的前缀最大值之和。
【样例输入】
5 666 Copy
【样例输出】
3408
【提示】
数列为{666,304,692,188,596}，前缀最大值为{666,666,692,692,692},和为3408。
【题解】前缀最小值
【题目描述】
求一个数列的所有前缀最小值之和。
即：给出长度为n的数列a[i],求出对于所有1<=i<=n，min(a[1],a[2],...,a[i])的和。
由于读入较大，数列由随机种子生成。
其中a[1]=x，a[i]=(379*a[i-1]+131)%997。
【输入描述】
一行两个正整数n,x，分别表示数列的长度和随机种子。(n<=100000,x<997)
【输出描述】
一行一个正整数表示该数列的前缀最小值之和。
【样例输入】
5 666
【样例输出】
1650
【提示】
数列为{666,304,692,188,596}，前缀最小值为{666,304,304,188,188},和为1650。
前缀最小：
比如，有数列：666 304 692 188 596，前缀最大值为：666,304,304,188,188，和为1650。
对于每个位置的前缀最小值解释如下：对于第1个数666，只有一个数，一定最大；对于第2个数，求出前两个数的最小数，还是304；对于第3个数，求出前3个数的最小数是304……其余位置依次类推，最后求前缀最小值得和。