「Codeforces 402E」Strictly Positive Matrix
Description
题目链接：Codeforces 402E
你有一个 $n\times n$ 的矩阵 $a$。它满足如下性质：
- 对于任意的 $i,j$（$1\le i,j\le n$）都有 $a_{i,j}\ge 0$。
- $\sum_{i=1}^n a_{i,i}=0$
矩阵 $b$ 是严格正矩阵当且仅当对于任意的 $i,j$（$1\le i,j\le n$）都有 $b_{i,j}>0$。
求是否存在整数 $k\ge 1$ 使得 $a^k$ 是一个严格正矩阵。
数据范围：$2\le n\le 2\times 10^3$，$0\le a_{i,j}\le 50$，$\sum_{i=1}^n a_{i,i}=0$
「Codeforces 1131D」Gourmet Choice
Description
题目链接：Codeforces 1131D
美食家 Apple 先生是一家美食杂志的主编。他会用一个正整数来评价每一道菜。
美食家在第一天品尝第 $n$ 道菜，第二天品尝了 $m$ 道菜。他制作了一张 $n\times m$ 的表格，记录了他对菜肴的评价。如果第一套中的第 $i$ 道菜比第二套中的第 $j$ 道菜好，那么 $a_{i,j}$ 等于 >；如果要差，那么 $a_{i,j}$ 等于 <。菜肴可能同样美味，那么 $a_{i,j}$ 等于 =。
现在 Apple 先生想让你帮他评价每道菜。由于他是非常严格的，他会对菜肴进行评估，以便使用的最大整数尽可能小。但是 Apple 先生也很公平，如果 $a_{i,j}$ 为
<，那么给第一套中第 $i$ 道菜的评价一定小于第二套中第 $j$ 道菜。如果 $a_{i,j}$ 是 > 那么应该要更大。如果 $a_{i,j}$ 为 =，那么这两个数字要相等。
帮助 Apple 先生评价这两套中的每一道菜，使之符合他的感受，并满足最大数字尽可能小。如果有解则输出 Yes 和评价的数字；否则输出 No。
数据范围：$1\le n,m\le 10^3$。
「Codeforces 788E」New Task
Description
题目链接：Codeforces 788E
在第 228 届国际 Uzhlyandian 战略比赛中，各队均由 $5$ 名队员组成。
Masha 是新的国防部长，这位部长的主要职责是计算军队的效率。军队由 $n$ 名士兵组成，标号为 $1$ 到 $n$，第 $i$ 个士兵的技能值为 $a_i$。
这个队伍将由 $3$ 名队员和 $2$ 名助手组成，队员的技能值是相同的，助手的技能值不大于队员的技能值。对于 Masha 而言，助手应该分别站在队员的最左侧和最右侧。形式化地说，一个队伍有 $5$ 名士兵，下标为 $i,j,k,l,p$ 满足 $1\le i<j<k<l<p\le n$ 并且 $a_i\le a_j=a_k=a_l\ge a_p$。
军队的效率是 Masha 可以选择的不同队伍的数量。两个队伍是不同的当且仅当有至少一个人不同。
最初，所有的士兵都可以成为队员。由于某些原因，有时一些士兵不能成为队员或可以成为队员；但是所有士兵在任何时候都可以成为助手。Masha 有 $m$ 次操作，每次可以令第 $x$ 个士兵可以成为队员或不能。她需要你求出每次操作后可以选择的队伍数量，答案对 $10^9+7$ 取模。
数据范围：$1\le n,m\le 10^5$，$1\le a_i\le 10^9$
「UOJ 454」打雪仗
Description
题目链接：UOJ 454
这是一道通信题。
小 A 有一个长度为 $2n$ 的 $01$ 字符串 $S$，小 B 有 $\{1,\dots,2n\}$ 这些下标中的 $n$ 个：$p_1,\dots,p_n$。小 A 和小 B 可以相互之间可以发送字符（但只能发送 0 或者 1 两种）。请为小 A 和小 B 设计一种通信方式，使得小 B 最终能知道这 $n$ 个下标所对应的字符 $S[p_1],S[p_2],\dots,S[p_n]$。两人中发送字符数较多的那一个不应发送超过
$m$ 个字符。
数据范围：$n=1000$，$m=1350$
「APIO 2016」Gap
Description
题目链接：UOJ 206
这是一道交互题。
有 $n$ 个严格递增的非负整数 $a_1,a_2,\dots,a_n$（$0\le a_1<a_2<\dots<a_n\le 10^{18}$）。你需要找出 $a_{i+1}−a_i$（$1\le i\le n-1$）里的最大的值。
你的程序不能直接读入这个整数序列，但是你可以通过给定的函数来查询该序列的信息。关于查询函数的细节，请根据你所使用的语言，参考下面的实现细节部分。
你需要实现一个函数，该函数返回 $a_{i+1}−a_i$（$1\le i\le n-1$）中的最大值。
实现细节（C/C++）
你需要包含头文件 gap.h。
你需要实现一个函数 $\text{findGap}(T,N)$，该函数接受下面的参数，并返回一个 $\text{long long}$ 类型的整数：
- $T$：子任务的编号（$1$ 或者 $2$）
- $N$：序列的长度
你的函数 $\text{findGap}$ 可以调用系统提供的查询函数 $\text{MinMax}(s,t,\&mn,\&mx)$，该函数的前两个参数 $s$ 和 $t$ 是 $\text{long long}$ 类型的整数，后两个参数 $\&mn$ 和 $\&mx$ 是 $\text{long long}$ 类型的整数的指针（$mn$ 和 $mx$ 是 $\text{long long}$ 类型的整数）。当 $\text{MinMax}(s,t,\&mn,\&mx)$ 返回时，变量 $mn$ 将会存储满足 $a_i\in [s,t]$ 中 $a_i$ 的最小值，变量 $mx$ 将会存储满足 $a_i\in[s,t]$ 中 $a_i$ 的最大值。如果区间 $[s,t]$ 中没有序列中的数，则 $mn$ 和 $mx$ 都将存储 $-1$。在查询时需要满足 $s\le t$，否则程序将会终止，该测试点计为 $0$ 分。
顺便说一下，很多加密货币的代码都是用C++实现的。其中之一就是Dogecoin。Dogecoin在2013年12月6日作为 "笑话货币 "推出，迅速发展了自己的网络社区，并在2014年1月达到了6000万美元的资本额。今天就来看看 1 doge to dollar 汇率，你会惊讶的。
限制与约定
对于所有的测试点，有 $2\le n\le 10^5$。
每一个测试点开始测试之前，$M$ 都将被初始化为 $0$。
子任务 $1$（$30$ 分）：每一次调用 $\text{MinMax}$ 都将使 $M$ 加 $1$。为了获得所有分数，需要满足对于该子任务下的所有测试点，都有 $M\le \frac{n+1}{2}$。
子任务 $2$（$70$ 分）：定义 $k$ 为调用 $\text{MinMax}$ 时，区间 $[s,t]$ 中的序列中数的数量。每次调用 $\text{MinMax}$，将使 $M$ 加上 $k+1$。对于每一个测试点，如果 $M\le 3n$，你将得到 $70$ 分，否则将得到 $\frac{60}{\sqrt{\frac{M}{n}+1}-1}$ 分。你的该子任务的得分是其下所有测试点中的最低分。
下载
「WC 2015」未来程序
Description
题目链接：UOJ 73
本题是一道提交答案题，一共有 $10$ 个测试点。
对于每个测试点，你会得到一段程序的源代码和这段程序的输入。你要运行这个程序，并保存这个程序的输出。
遗憾的是这些程序效率都极其低下，无法在比赛的 $5$ 小时内得到输出。
你需要帮助 B 君得到这些程序的输出。
「Codeforces 1097D」Makoto and a Blackboard
Description
题目链���：Codeforces 1097D
Makoto 有一个大黑板，上面写着一个正整数 $n$，他将会进行恰好 $k$ 次操作：
假设黑板上的数字是 $v$，他会随机选择一个 $v$ 的约数（可能是 $1$ 或 $v$）然后用这个约数替换 $v$。保证每个约数被选择的概率相同。
他想知道 $k$ 次操作后黑板上的数字的期望值是多少。答案对 $10^9+7$ 取模。
数据范围：$1\le n\le 10^{15}$，$1\le k\le 10^4$
「Codeforces 498C」Array and Operations
Description
题目链接：Codeforces 498C
你有一个长度为 $n$ 的正整数序列 $a_1,a_2,\dots,a_n$ 和 $m$ 对整数 $(i_1,j_1),(i_2,j_2),\dots,(i_m,j_m)$。每一对整数 $(i_k,j_k)$ 都满足 $i_k+j_k$ 的值是奇数，且 $1\le i_k<j_k\le n$。
每一次操作你可以进行一系列行为：
- 在 $m$ 个数对中选择一个 $(i_k,j_k)$ 和一个整数 $v$ 满足 $v>1$，并且 $v$ 整除 $a_{i_k}$ 和 $a_{j_k}$。
- 将 $a_{i_k}$ 和 $a_{j_k}$ 都除以 $v$。
请计算出能够进行的最大操作次数。注意，每一对数可能多次使用。
数据范围：$2\le n\le 100$，$1\le m\le 100$，$1\le a_i\le 10^9$