某班级有8名男生和6名女生，现要选出3人组成学习小组，要求小组中至少有1名男生和1名女生，则不同的选法共有（ ）种。

在杨辉三角中，从第0行开始计数，第10行的所有数之和为（ ）。

下列代码实现了快速幂算法，其时间复杂度为（ ）。

long long fastPow(long long b, long long e, long long mod) {
long long result = 1;
while (e > 0) {
if (e & 1)
result = result * b % mod;
b = b * b % mod;
e >>= 1;
}
return result;
}

从5本不同的数学书和4本不同的物理书中选取3本书，要求至少包含1本数学书，则不同的选法有（ ）种。

在二叉搜索树(BST)中，若中序遍历的序列为{1,2,3,4,5}，且先序遍历的第一个序列元素为3，则下列说法正确的是（ ）。

在一个有向带权图中，使用Dijkstra算法求单源最短路时，若使用优先队列（小根堆）优化，其时间复杂度为（ ）。

对于含n个顶点（n≥2）的连通加权有向图，若图中不存在负权环，则任意两点之间的最短路径（简单路径）最多包含（ ）条边。

在使用Floyd算法求任意两点间最短路径时，时间复杂度为O(V³)。若在某次算法执行前，已经用Dijkstra算法正确求出了所有点对的最短路并存入了dist数组如果此时继续对该 dist 数组执行一次完整的 Floyd 算法过程 （无任何提前终止），执行完毕后 dist 数组内的值（ ）。

关于图论中的最短路径算法，下列说法中严格正确的是（ ）。

有6个人排成一排照相，其中甲、乙两人必须相邻，且丙不能站在排头的不同排法有（ ）种。

下列代码试图实现Floyd算法求所有点对之间的最短路径，横线处应填入（ ）。

void floyd(int n, int dist[][MAXN]) {
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (______)
dist[i][j] = dist[i][k] + dist[k][j];
}

用数字0、1、2、3、4组成无重复数字的五位偶数，共有（ ）个。

在一个无向带权图中，若使用Prim算法从顶点0开始构造最小生成树（边权均为正整数，且graph[u][v]==0表示无边），下列代码中横线处应填入（ ）。

for (int v = 0; v < n; v++) {
if (______) {
minEdge[v] = graph[u][v];
parent[v] = u;
}
}

已知三个点A(x1,y1)、B(x2,y2)、C(x3,y3)在平面直角坐标系中的坐标。下列C++表达式中，在精度误差范围1e-8内能正确判断这三个点是否三点共线的表达式是（ ）。

在64位操作系统下（LP64/LLP64模型），下面代码的输出结果是（ ）。

#include <iostream>
using namespace std;
int main() {
int a[4] = {1, 2, 3, 4};
int (*p)[4] = &a;
int* q = a;
cout << sizeof(a) << " ";
cout << sizeof(p) << " ";
cout << sizeof(p + 1) << " ";
cout << sizeof(q + 1) << " ";
cout << (p + 1) - p << " ";
cout << (q + 1) - q << endl;
}

在C++中，若结构体中包含一个static成员变量，则该变量的存储空间属于结构体对象的一部分。

对于任意正整数n，二项式(a+b)^n展开式中各项的二项式系数之和等于2^n。

在C++中，若函数参数类型为const int&，则该参数既可以绑定左值，也可以绑定右值。

若一个无向图的最小生成树唯一，则图中所有边权必定各不相同。

使用快速排序对n个元素进行排序时，无论最好、最坏还是平均情况，时间复杂度均为O(nlogn)。

若一个图中所有顶点的度数为偶数，则一定存在欧拉回路。

使用倍增法预处理区间最值问题时，预处理的时间复杂度为O(nlogn)，查询的时间复杂度为O(1)。

如果将一个连通无向图G1中所有边的权值都统一增加同一个正整数常数C，形成图G2。则G1的最小生成树中每条边在G2中对应的边组成的树，一定是G2的最小生成树。

在图论算法中，Kruskal算法和Prim算法都可以用来求解最小生成树，且这两者的贪心策略无论在任何连通无向图上求得的最小生成树总边权和必定相同。

在动态规划问题中，"状态转移方程+递推"和"递归+记忆化搜索"通常是解决同一问题的两种不同实现方式，它们的时间复杂度总是相同的。

消息查找

时间限制：1.0s 内存限制：512.0MB
小A的消息记录中有n条消息，依次以1,2,...,n编号。编号小的消息发送时间早于编号大的消息。
一条消息可以引用一条编号小于它的消息，也可以不引用消息。
消息记录的一个例子是：
【消息1】小A：有人做了今天的第一题吗？

【消息2】小A：我第一题WA了，可能是什么原因？

【消息3：引用消息1】小B：我我我

【消息4：引用消息2】小C：我也WA了

【消息5：引用消息2】小B：是不是没开long long？

【消息6：引用消息5】小A：改了就AC了，太厉害了！
对于消息i(1≤i≤n)，小A以ri标记消息i是否有引用。如果ri>0，则消息i为引用了消息ri；如果ri=0，则消息i没有引用消息。
消息查找工具任意时刻只能定位恰好一条消息。如果当前位于消息i(1<i≤n)，可以选择：1.定位到消息i-1；2.如果消息i引用了消息ri，定位到消息ri。
小A有q次询问。在第k次询问中，小A给出消息编号xk、yk(yk<xk)。小A想知道，如果当前消息查找工具位于xk，至少需要多少次操作才能定位到消息yk。

第一行，两个正整数n、q。第二行，n个非负整数r₁,r₂,...,rₙ。接下来q行描述询问。

输出q行，每行一个整数，表示从消息xk切换到消息yk所需的最少操作次数。

【样例输入1】
6 3
0 0 1 2 2 5
4 1
6 2
6 3
【样例输出1】
3
4
3
对于所有测试点，保证1≤n≤10⁵，1≤q≤10⁵，0≤ri<i，1≤yk<xk≤n，保证至多有1000条引用消息。

子图最短路

时间限制：1.0s 内存限制：512.0MB
给定包含n个结点m条边的带权无向图G，结点依次以1,2,...,n编号。
第i(1≤i≤m)条边连接编号为ui与vi的两个结点，权值为wi。
对于指定的1≤l≤r≤n，按以下方式构造图G的子图G(l,r)：
保留G中编号在区间[l,r]中的结点。删去其它编号不在[l,r]中的结点以及与之相连的边。
对于G(l,r)中的任意结点u,v应有l≤u,v≤r。记u,v在子图G(l,r)上的最短距离为d(l,r,u,v)。
特殊地，若u,v在子图G(l,r)上不连通，则认为d(l,r,u,v)=∞。
你需要求出∑₁ₗ₌₁ⁿ∑ᵤ₌ₗʳd(l,r,u,v)对10⁹取模的结果。

第一行，两个正整数n、m。接下来m行描述边。

输出一行，一个整数，表示结果对10⁹取模的值。

【样例输入1】
3 2
1 2 1
2 3 2
【样例输出1】
8
对于所有测试点，保证2≤n≤100，2≤m≤n，1≤ui,vi≤n，1≤wi≤10⁹。图中可能存在重边。