题意描述

洛谷链接

LibreOJ 链接

给定整数 \(g\)，\(n\)（\(1 \leq q, n \leq 10^9\)），计算：

\[ g^{\sum_{d|n}{C_{n}^{d}}} \operatorname{mod} 999911659 \]

题意描述

洛谷链接

\(N\) 个柱子排成一排，一开始每个柱子损伤度为 0。

接下来勇仪会进行 \(M\) 次攻击，每次攻击可以用 4 个参数\(l\),\(r\),\(s\),\(e\)来描述：

表示这次攻击作用范围为第 \(l\) 个到第 \(r\) 个之间所有的柱子（包含 \(l\)，\(r\)），对第一个柱子的伤害为 \(s\)，对最后一个柱子的伤害为 \(e\)。

攻击产生的伤害值是一个等差数列。若 \(l = 1\)，\(r = 5\)，\(s = 2\)，\(e = 10\)，则对第 1 ~ 5 个柱子分别产生 2, 4, 6, 8, 10 的伤害。

鬼族们需要的是所有攻击完成之后每个柱子的损伤度。

题目描述

Codeforces 链接

Treeland 国有 \(n\) 个城市，这 \(n\) 个城市连成了一颗树，有 \(n - 1\) 条道路连接了所有城市。每条道路只能单向通行。现在政府需要决定选择哪个城市为首都。假如城市 i 成为了首都，那么为了使首都能到达任意一个城市，不得不将一些道路翻转方向，记翻转道路的条数为 \(k\)。你的任务是找到所有满足 \(k\) 最小的首都。

题意描述

洛谷链接

我们已知 \(n\) 对夫妻的婚姻状况，称第 \(i\) 对夫妻的男方为 \(B_i\)，女方为 \(G_i\)。若某男 \(B_i\) 与某女 \(G_j\) 曾经交往过（无论是大学，高中，亦或是幼儿园阶段，\(i \le j\)），则当某方与其配偶（即 \(B_i\) 与 \(G_i\)或 \(B_j\) 与 \(G_j\)）感情出现问题时，他们有私奔的可能性。不妨设 \(B_i\) 和其配偶 \(G_i\) 感情不和，于是 \(B_i\) 和 \(G_j\) 旧情复燃，进而 \(B_j\) 因被戴绿帽而感到不爽，联系上了他的初恋情人 \(G_k\)……一串串的离婚事件像多米诺骨牌一般接踵而至。若在 \(B_i\) 和 \(G_i\) 离婚的前提下，这 \(2n\) 个人最终依然能够结合成 \(n\) 对情侣，那么我们称婚姻 \(i\) 为不安全的，否则婚姻 \(i\) 就是安全的。

给定所需信息，你的任务是判断每对婚姻是否安全。

题意描述

洛谷链接

一些学校连入一个电脑网络。那些学校已订立了协议：每个学校都会给其它的一些学校分发软件（称作“接受学校”）。注意即使 \(B\) 在 \(A\) 学校的分发列表中，\(A\) 也不一定在 \(B\) 学校的列表中。

你要写一个程序计算，根据协议，为了让网络中所有的学校都用上新软件，必须接受新软件副本的最少学校数目（子任务 A）。更进一步，我们想要确定通过给任意一个学校发送新软件，这个软件就会分发到网络中的所有学校。为了完成这个任务，我们可能必须扩展接收学校列表，使其加入新成员。计算最少需要增加几个扩展，使得不论我们给哪个学校发送新软件，它都会到达其余所有的学校（子任务 B）。一个扩展就是在一个学校的接收学校列表中引入一个新成员。

鸽了好久

概念

强连通图：指的是一张有向图，其中从任意一个节点出发，都可达到该图的所有节点。

强连通分量：指的是有向图的一种子图，满足该子图为强连通图，且这个子图是 极大 的，即对于一幅图 \(G\) 的强连通分量 \(G_0\)，我们无法找到一副子图 \(G_1\) 为强连通图，且满足 \(G_0 \subsetneqq G_1 \subseteq G\)

题意描述

洛谷链接

LibreOJ 链接

对于该题，你需要展开 #define 宏定义。本题中的宏定义与 C++ 中的宏定义大致相同，不过有下列特点：

• 可以用 #undef 取消宏定义；
• 可以进行多次展开。如 #define a b+e，#define b c+d，对于 a 最终展开结果为 c+d+e；
• 可以进行递归展开，但若待展开的宏名与正在进行展开的某个宏名相同，为了防止无限递归，此时宏名就不再展开。如 #define a b+c，#define b a+a，对于 b 的展开结果即为 b+c+b+c。

其他细节详见题面。

题意描述

洛谷链接

将一个 \(8 \times 8\) 的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的两部分中的任意一块继续如此分割，这样割了 \(n - 1\) 次后，连同最后剩下的矩形棋盘共有 \(n\) 块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)

原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成 \(n\) 块矩形棋盘，并使各矩形棋盘总分的平方和最小。

请编程对给出的棋盘及 \(n\) ，求出平方和的最小值。

数据范围：\(1 \leq n \leq 15\)

题意描述

洛谷链接

LibreOJ 链接

司令部的将军们打算在 \(N \times M\) 的网格地图上部署他们的炮兵部队。一个 \(N \times M\) 的地图由 \(N\) 行 \(M\) 列组成，地图的每一格可能是山地（用 H 表示），也可能是平原（用 P 表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：

如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。

现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。

数据范围：\(N \leq 100\)，\(M \leq 10\)

题意描述

洛谷链接

有一个球形空间产生器能够在 \(n\) 维空间中产生一个坚硬的球体。现在，你被困在了这个 \(n\) 维球体中，你只知道球面上 \(n + 1\) 个点的坐标，你需要以最快的速度确定这个 \(n\) 维球体的球心坐标，以便于摧毁这个球形空间产生器。