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

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

#include
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小A有q次询问。在第k次询问中，小A给出消息编号xk、yk(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⁹。图中可能存在重边。