yl-9/probench huggingface dataset:
# 数论

## 题目描述

有 $T$ 次询问，每次给定正整数 $n,k$，求 

$\prod_{i=k}^n \varphi\left(\binom{i}{k}\right).$ 

你只需要输出答案对 $10^9+7$ 取模后的值即可。 

## 输入描述:
    
    
    第一行，一个正整数 $T$，表示数据组数。
    
    接下来 $T$ 行，每行两个正整数 $n,k$。

## 输出描述:
    
    
    $T$ 行，每行一个非负整数，表示答案。

示例1 

## 输入
    
    
    5
    1 1
    4 2
    5 3
    10 3
    1000 20

## 输出
    
    
    1
    4
    8
    28311552
    301294499

## 备注:

  * $1\le T\le 10^4$；
  * $1\le n\le 10^7$；
  * $1\le k\le \min(n,5000)$。




## 时空限制

时间限制：C/C++/Rust/Pascal 8秒，其他语言16秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

Tags: 组合数学, 数据结构, 分块, 枚举, 位运算, 数论
Difficulty: 3100
# 彩虹糖的梦

## 题目描述

$\hspace{15pt}$有红橙黄绿青蓝紫七种不同颜色的彩虹糖，第 $i$ 种颜色的彩虹糖有 $a_i$ 个。  
  
$\hspace{15pt}$每一位小朋友都想要吃到全部七种颜色的彩虹糖。最多可以分给多少个小朋友？

## 输入描述:
    
    
    $\hspace{15pt}$第一行输入七个整数 $a_1, a_2, \dots, a_7\left(1 \leq a_i \leq 10^9\right)$ 代表七种颜色的彩虹糖数量。

## 输出描述:
    
    
    $\hspace{15pt}$在一行上输出一个整数，代表最多可以分给多少个小朋友。

示例1 

## 输入
    
    
    1 1 1 1 1 1 1

## 输出
    
    
    1

## 说明
    
    
    $\hspace{15pt}$红橙黄绿亲兰子，每种颜色的彩虹糖各 $1$ 个，所以最多可以分给 $1$ 位小朋友。

示例2 

## 输入
    
    
    2 3 4 5 6 7 8

## 输出
    
    
    2

## 说明
    
    
    $\hspace{15pt}$由于红色的彩虹糖只有 $2$ 个，所以最多可以分给 $2$ 位小朋友。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 球格模型（简单版）

## 题目描述

$\hspace{15pt}$对于 $n$ 行 $m$ 列的网格，一共有 $n \times m$ 个格子。  
  
$\hspace{15pt}$现在，一共有 $k$ 个小球，小球需要全部放入格子中，单个格子可以放置多个小球，也可以不放。  
  
$\hspace{15pt}$你只需要输出任意一种符合条件的摆放方式；使得任意行、任意列均至少有一个小球。特别地，如果不存在这样的摆放方式，直接输出 $-1$ 。

## 输入描述:
    
    
    $\hspace{15pt}$在一行上输入三个整数 $n,m,k\left(1\leqq n,m,k\leqq 10^6;\ n \times m \leqq 10^6\right)$ 代表网格的行数、网格的列数、小球数量。

## 输出描述:
    
    
    $\hspace{15pt}$如果不存在符合条件的摆放方式，直接输出 $-1$ ；否则，输出 $n$ 行 $m$ 列的矩阵，代表一种符合条件的摆放方式。矩阵第 $i$ 行第 $j$ 列的元素 $a_{i,j} \left(0\leqq a_{i,j} \leqq k\right)$ 代表第 $i$ 行第 $j$ 列的格子中放置的小球数量。  
      
    $\hspace{15pt}$如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

示例1 

## 输入
    
    
    2 2 2

## 输出
    
    
    0 1
    1 0

## 说明
    
    
    $\hspace{15pt}$在这个样例中，我们一共有两种不同的摆放方式：$\begin{bmatrix}
     0 & 1 \\
     1 & 0
    \end{bmatrix}$ 、$\begin{bmatrix}
     1 & 0 \\
     0 & 1
    \end{bmatrix}$ 。

示例2 

## 输入
    
    
    2 2 3

## 输出
    
    
    0 1
    2 0

## 说明
    
    
    $\hspace{15pt}$在这个样例中，符合条件的摆放方式有：$\begin{bmatrix}
     0 & 1 \\
     1 & 1
    \end{bmatrix}$ 、$\begin{bmatrix}
     1 & 0 \\
     1 & 1
    \end{bmatrix}$ 、$\begin{bmatrix}
     1 & 1 \\
     0 & 1
    \end{bmatrix}$ 、$\begin{bmatrix}
     1 & 1 \\
     1 & 0
    \end{bmatrix}$ 、$\begin{bmatrix}
     2 & 0 \\
     0 & 1
    \end{bmatrix}$ 、$\begin{bmatrix}
     1 & 0 \\
     0 & 2
    \end{bmatrix}$ 、$\begin{bmatrix}
     0 & 2 \\
     1 & 0
    \end{bmatrix}$ 、$\begin{bmatrix}
     0 & 1 \\
     2 & 0
    \end{bmatrix}$ 。

示例3 

## 输入
    
    
    6 6 1

## 输出
    
    
    -1


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld
# 小数字

## 题目描述

$\hspace{15pt}$小娴给阿笙出了一种简单数学题，小娴给出数字 $n$ ，并规定三种操作：  
  
$\hspace{23pt}\bullet\,$若 $n$ 为非负整数，开根号（向上取整），即 $n \to \lceil \sqrt{n} \rceil$ ；  
$\hspace{23pt}\bullet\,$对当前的数字 $n$ 减 $1$ ，即 $n \to n - 1$；  
$\hspace{23pt}\bullet\,$对当前数字除以 $2$（向上取整），即 $n \to \lceil \frac{n}{2} \rceil$；  
  
$\hspace{15pt}$现在可以对数字 $n$ 操作 $m$ 次，小娴想让阿笙计算出操作 $m$ 次之后 $n$ 最小可以为多少。

## 输入描述:
    
    
    $\hspace{15pt}$每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\leqq T\leqq 2 \times 10^5\right)$ 代表数据组数，每组测试数据描述如下：  
      
    $\hspace{15pt}$在一行上输入两个整数 $n,m\left(1\leqq n, m\leqq 10^9\right)$ 代表初始数字、操作次数。

## 输出描述:
    
    
    $\hspace{15pt}$对于每一组测试数据，在单独的一行上输出一个整数，代表操作 $m$ 次之后 $n$ 最小可以为多少。

示例1 

## 输入
    
    
    3
    10 1
    2 1
    2 100

## 输出
    
    
    4
    1
    -98

## 说明
    
    
    $\hspace{15pt}$对于第一组测试数据，三种操作得到的答案依次为：$10 \to \lceil \sqrt{10} \rceil = 4$ ；$10 \to 10 - 1  = 9$ ；$10 \to \lceil \frac{10}{2} \rceil = 5$ 。综上，最小答案为 $4$ 。  
      
    $\hspace{15pt}$对于第二组测试数据，三种操作得到的答案依次为：$2 \to \lceil \sqrt{2} \rceil = 2$ ；$2 \to 2 - 1  = 1$ ；$2 \to \lceil \frac{2}{2} \rceil = 1$ 。综上，最小答案为 $1$ 。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 预知

## 题目描述

$\hspace{15pt}$牌桌上有 $n$ 种不同的卡牌，第 $i$ 种卡牌有 $a_i$ 张。初始时，所有的卡牌均背面朝上，但不知道其确切的种类。你有两次翻牌机会，翻牌后，如果两张卡牌种类一致，那你就输了。**两次翻牌同时进行** （不存在根据翻开的第一张牌更改策略的情况）。  
  
$\hspace{15pt}$你不喜欢运气游戏，所以你可以通过手段**随机** 预知 $k$ 张卡牌后再进行游玩。  
  
$\hspace{15pt}$然而，预知很累！你想要知道，你至少需要预知多少张卡牌，才能保证你不会输。

## 输入描述:
    
    
    $\hspace{15pt}$每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\leqq T\leqq 2 \times 10^5\right)$ 代表数据组数，每组测试数据描述如下：  
      
    $\hspace{15pt}$第一行输入一个整数 $n\left(1\leqq n\leqq 2 \times 10^5\right)$ 代表卡牌种类数。  
    $\hspace{15pt}$第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n\left(1\leqq a_i\leqq 10^9\right)$ 代表每种卡牌数量。  
      
    $\hspace{15pt}$除此之外，保证每一组测试数据的卡牌总数之和不小于 $2$ ；单个测试文件的 $n$ 之和不超过 $2 \times 10^5$ 。

## 输出描述:
    
    
    $\hspace{15pt}$对于每一组测试数据，如果没有必胜策略，直接输出 $-1$ ；否则，在单独的一行上输出一个整数，代表你至少需要预知多少张卡牌，才能保证你不会输。

示例1 

## 输入
    
    
    3
    2
    1 1
    1
    10
    2
    2 3

## 输出
    
    
    0
    -1
    3

## 说明
    
    
    $\hspace{15pt}$对于第一组测试数据，只有两张卡牌，且各不相同，直接翻开即可。  
      
    $\hspace{15pt}$对于第二组测试数据，由于卡牌种类唯一，不管怎么翻都会输。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 而后单调

## 题目描述

$\hspace{15pt}$对于给定的由 $n$ 个整数组成的数组 $\left\\{a_1, a_2, \dots, a_n\right\\}$ ，你需要按照下述规则进行操作：  
  
${\hspace{20pt}}_\texttt{1.}\,$从数组中选出连续的 $m$ 个元素（即选择一个长度为 $m$ 的连续子数组）；  
  
${\hspace{20pt}}_\texttt{2.}\,$将数组中剩余的 $n - m$ 个元素重新排序；  
  
${\hspace{20pt}}_\texttt{3.}\,$在重新排序后的数组中选择一个位置，顺序插入刚刚选出的 $m$ 个元素；  
  
$\hspace{15pt}$问是否存在至少一种方案，使得最终得到的数组是个严格递增或严格递减数组。

## 输入描述:
    
    
    $\hspace{15pt}$每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\leqq T\leqq 2 \times 10^5\right)$ 代表数据组数，每组测试数据描述如下：  
      
    $\hspace{15pt}$第一行输入两个整数 $n,m\left(1\leqq n \leqq 2 \times 10^5;\ 1\leqq m \leqq n\right)$ 代表数组长度、你需要取出的元素数量。  
    $\hspace{15pt}$第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n\left(1\leqq a_i\leqq 10^9\right)$ 代表数组元素。  
      
    $\hspace{15pt}$除此之外，保证单个测试文件的 $n$ 之和不超过 $2 \times 10^5$ 。

## 输出描述:
    
    
    $\hspace{15pt}$对于每一组测试数据，如果存在至少一种方案，使得最终得到的数组是个严格递增或严格递减数组，在单独的一行上输出 $\textrm{YES}$ ；否则，直接输出 $\textrm{NO}$ 。

示例1 

## 输入
    
    
    4
    5 5
    1 2 3 4 5
    3 2
    9 2 4
    6 3
    12 3 8 7 6 5
    5 3
    1 3 2 4 5

## 输出
    
    
    YES
    YES
    YES
    NO

## 说明
    
    
    $\hspace{15pt}$对于第一组测试数据，不需要进行任何操作，数组已经是严格递增数组。  
      
    $\hspace{15pt}$对于第二组测试数据，选择区间 $[2,3]$ ，随后将这两个元素插入到 $9$ 之前，得到 $\{{\color{orange}2}, {\color{orange}4}, 9\}$ 。  
      
    $\hspace{15pt}$对于第三组测试数据，符合要求的方案为，选择区间 $[3,5]$ ，随后将剩余的元素重新排列得到 $\{12, 5, 3\}$ ，随后将这三个元素插入到 $12$ 之后，得到 $\{12, {\color{orange}8}, {\color{orange}7}, {\color{orange}6}, 5, 3\}$ 。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 最大最小路

## 题目描述

$\hspace{15pt}$对于给定的无向无根树，第 $i$ 个节点上有一个权值 $w_i$ 。我们定义一条简单路径是好的，当且仅当：路径上的点的点权最小值小于等于 $a$ ，路径上的点的点权最大值大于等于 $b$ 。  
  
$\hspace{15pt}$保证给定的 $a < b$ ，你需要计算有多少条简单路径是好的。

## 输入描述:
    
    
    $\hspace{15pt}$第一行输入三个整数 $n, a, b\left(1 \leq n \leq 5 \times 10^5, 1 \leq a < b \leq 10^9\right)$ 代表节点数、给定的上下限。  
      
    $\hspace{15pt}$第二行输入 $n$ 个整数 $w_1, w_2, \dots, w_n\left(1 \leq w_i \leq 10^9\right)$ 代表每个节点的权值。  
      
    $\hspace{15pt}$此后 $n - 1$ 行，每行输入两个整数 $u, v\left(1 \leq u, v \leq n, u \neq v\right)$ 代表一条无向边连接树上 $u$ 和 $v$ 两个节点。

## 输出描述:
    
    
    $\hspace{15pt}$在一行上输出一个整数，代表好路径的条数。

示例1 

## 输入
    
    
    5 2 3
    5 4 3 3 1
    1 2
    1 3
    3 4
    3 5

## 输出
    
    
    4

## 说明
    
    
    $\hspace{15pt}$对于这个样例，如下图所示。路径 $2 \to 1 \to 3 \to 5$ 是好的，因为路径点权最小值 $1 \leqq a$ 且点权最大值 $5 \geqq b$ 。  
      
    ![](https://uploadfiles.nowcoder.com/images/20241225/0_1735120866477/1F486A0DAECBAE0170FACC49BD05D782)  
    $\hspace{15pt}$除此之外，以下路径也是好的：  
    $\hspace{23pt}\bullet\,$$1 \to 3 \to 5$ ；  
    $\hspace{23pt}\bullet\,$$3 \to 5$ ；  
    $\hspace{23pt}\bullet\,$$4 \to 3 \to 5$ 。


## 时空限制

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 小红的正整数构造

## 题目描述

$\hspace{15pt}$小红拿到了一个区间$[l,r]$，她希望你在这个区间内找到一个正整数，满足该正整数是 $x$ 的倍数。你能帮帮她吗？  


## 输入描述:
    
    
    $\hspace{15pt}$在一行上输入三个正整数 $l,r,x \left(1\leq l \leq r \leq 100;\ 1\leq x \leq 100\right)$ 代表区间的左右边界、基础倍数。  
    

## 输出描述:
    
    
    $\hspace{15pt}$如果存在这样的正整数，在一行上输出它；否则，直接输出 $-1$ 。  
      
    $\hspace{15pt}$如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。  
    

示例1 

## 输入
    
    
    6 10 3

## 输出
    
    
    6

## 说明
    
    
    $\hspace{15pt}$输出 $9$ 也是可以的。  
    


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld
# 小红的区间构造

## 题目描述

$\hspace{15pt}$小红拿到了正整数 $x$ ，她希望你找到一个长度为 $k$ 的区间，满足区间内恰好有 $n$ 个数是 $x$ 的倍数。你能帮帮她吗？  


## 输入描述:
    
    
    $\hspace{15pt}$在一行上输入三个整数 $n,k,x \left(1\leq n,k,x \leq 10^9\right)$ 。

## 输出描述:
    
    
    $\hspace{15pt}$如果答案不存在，直接输出 $-1$ ；否则，输出两个正整数 $l,r \left(1\leq l \leq r < 2 \times 10^9;\ l + k - 1 = r\right)$ 代表答案。  
      
    $\hspace{15pt}$如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。  
    

示例1 

## 输入
    
    
    2 5 3

## 输出
    
    
    6 10

## 说明
    
    
    $\hspace{15pt}$在这个样例中，$[6,10]$ 区间内恰好有 $2$ 个数是 $3$ 的倍数，符合要求。  
    


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld
# 小红的排列构造

## 题目描述

$\hspace{15pt}$小红定义一个仅由 $\tt 0$ 和 $\tt 1$ 两个字符构成的 $\tt 01$ 串 $s$ 和一个 _排列_ $p$ 是匹配的，当且仅当满足以下条件：  
$\hspace{23pt}\bullet\,$ 若 $s_i = \tt 1$，则排列的前 $i$ 项元素恰好也构成一个排列；  
$\hspace{23pt}\bullet\,$ 若 $s_i = \tt 0$，则排列的前 $i$ 项元素无法构成一个排列；  
$\hspace{15pt}$现在小红拿到了一个长度为 $n$ 的 $\tt 01$ 串。请你构造一个排列使得它们是匹配的。  
  
$\hspace{15pt}$长度为 $n$ 的 _排列_ 是由 $1 \sim n$ 这 $n$ 个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如，$\\{2,3,1,5,4\\}$ 是一个长度为 $5$ 的排列，而 $\\{1,2,2\\}$ 和 $\\{1,3,4\\}$ 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。  


## 输入描述:
    
    
    $\hspace{15pt}$第一行输入一个正整数 $n \left(1\leq n\leq 10^5\right)$ 代表排列的长度。  
    $\hspace{15pt}$第二行输入一个长度为 $n$ 的 $\tt 01$ 字符串 $s$ 。  
    

## 输出描述:
    
    
    $\hspace{15pt}$如果答案不存在，直接输出 $-1$ ；否则，在一行上输出 $n$ 个正整数代表构造的排列。  
      
    $\hspace{15pt}$如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。  
    

示例1 

## 输入
    
    
    3
    001

## 输出
    
    
    3 1 2

## 说明
    
    
    $\hspace{15pt}$对于这个样例，  
    $\hspace{23pt}\bullet\,$由于 $s_0 = {\tt 0}$，排列的前一项元素无法构成一个排列；  
    $\hspace{23pt}\bullet\,$由于 $s_1 = {\tt 0}$，排列的前两项元素无法构成一个排列；  
    $\hspace{23pt}\bullet\,$由于 $s_2 = {\tt 1}$，排列的前三项元素构成一个排列；  
    $\hspace{15pt}$同时，输出 $\{2,3,1\}$、$\{3,2,1\}$ 等答案也都是合法的。  
    

示例2 

## 输入
    
    
    4
    1110

## 输出
    
    
    -1


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld
# 小红的01子序列构造（easy）

## 题目描述

$\hspace{15pt}$小红拿到了一个仅由 $\tt 0$ 和 $\tt 1$ 两个字符构成的 $\tt 01$ 串 $s$ ，她希望你找到一个区间，满足该区间内有恰好 $k$ 个 $\tt 01$ _子序列_ 。  
  
$\hspace{15pt}$_子序列_ 为从原字符串中删除任意个（可以为零、可以为全部）字符得到的新字符串。  


## 输入描述:
    
    
    $\hspace{15pt}$第一行输入两个整数 $n,k \left(1\leq n\leq 2 \times 10^5;\ 1\leq k \leq 10^{10}\right)$ 代表 $\tt 01$ 串的长度、希望寻找的 $\tt 01$ 子序列数量。  
      
    $\hspace{15pt}$第二行输入一个长度为 $n$ 的 $\tt 01$ 字符串 $s$ 。

## 输出描述:
    
    
    $\hspace{15pt}$如果答案不存在，直接输出 $-1$ ；否则，在一行上输出两个正整数 $l,r \left(1\leq l \leq r \leq n\right)$ 代表寻找到的区间是第 $l$ 个字符到第 $r$ 个字符对应的区间。  
      
    $\hspace{15pt}$如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。  
    

示例1 

## 输入
    
    
    4 2
    0011

## 输出
    
    
    1 3

## 说明
    
    
    $\hspace{15pt}$输出 $[2, 4]$ 也是可以的。  
    

示例2 

## 输入
    
    
    4 2
    1110

## 输出
    
    
    -1


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld
# 小红的二分图构造

## 题目描述

$\hspace{15pt}$小红希望你构造一个 _二分图_ ，满足第 $i$ 个节点的度数恰好等于 $d_i$ 。你能帮帮她吗？  
  
$\hspace{15pt}$_二分图_ 是一张满足如下条件的图：它的节点可以被分成两个不相交的集合 $U$ 与 $V$ ，使得图中的每一条边都连接 $U$ 中的一个节点与 $V$ 中的一个节点。  


## 输入描述:
    
    
    $\hspace{15pt}$第一行输入一个正整数 $n \left(1\leq n \leq 100\right)$ ，代表二分图的节点数量。  
    $\hspace{15pt}$第二行输入 $n$ 个正整数 $d_1, d_2, \cdots, d_n \left(1\leq d_i \leq n-1\right)$ ，代表每个节点的度数。  
    

## 输出描述:
    
    
    $\hspace{15pt}$如果答案不存在，直接输出 $-1$ 。  
      
    $\hspace{15pt}$否则，请参考下方的格式输出。  
    $\hspace{15pt}$第一行输出一个整数 $m$ 代表边的数量。  
    $\hspace{15pt}$接下来的 $m$ 行，每行输出两个正整数 $u,v \left(1\leq u,v \leq n\right)$ 代表节点 $u$ 和节点 $v$ 有一条边连接。  
    $\hspace{15pt}$构造的图可以包含重边，但不能包含自环。构造的最终的图可以不连通，你只需要保证每个连通分量均为二分图。  
      
    $\hspace{15pt}$如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。  
    

示例1 

## 输入
    
    
    3
    1 2 1

## 输出
    
    
    2
    1 2
    2 3

## 说明
    
    
    $\hspace{15pt}$构造的图是一棵树，显然所有树都是二分图。  
    

示例2 

## 输入
    
    
    3
    2 2 2

## 输出
    
    
    -1

## 说明
    
    
    $\hspace{15pt}$只能构造一个三元环，显然不是二分图。  
    


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld
# 小红的01子序列构造（hard）

## 题目描述

$\hspace{15pt}$小红希望你构造一个长度为 $n$ 的 $\tt 01$ 串，满足 $m$ 个性质：对于 $i \in [1, m]$ ，区间 $[l_i, r_i]$ 有恰好 $x_i$ 个 $\tt 0$ ，$y_i$ 个 $\tt 1$ ，$k_i$ 个 $\tt 01$ _子序列_ 。  
$\hspace{15pt}$给定的限制区间为两两包含关系。即对于 $i \neq j$ ，若 $l_i \leq l_j$ ，则 $r_i \geq r_j$ ，反之亦然。  
  
$\hspace{15pt}$_子序列_ 为从原字符串中删除任意个（可以为零、可以为全部）字符得到的新字符串。

## 输入描述:
    
    
    $\hspace{15pt}$第一行输入两个正整数 $n,m \left(1\leq n,m \leq 10^5\right)$ 代表 $\tt 01$ 串的长度、限制的数量。  
    $\hspace{15pt}$接下来的 $m$ 行，每行输入五个非负整数 $l_i,r_i,x_i,y_i,k_i \left(1\leq l_i \leq r_i \leq n;\ 0\leq k_i \leq 10^{10};\ 0\leq x_i,y_i \leq r_i-l_i+1;\ x_i+y_i=r_i-l_i+1\right)$ ，代表构造的 $\tt 01$ 串需满足区间 $[l_i,r_i]$ 有恰好 $x_i$ 个 $\tt 0$ ，$y_i$ 个 $\tt 1$ ，$k_i$ 个 $\tt 01$ 子序列。  
    $\hspace{15pt}$保证给定的任意两个区间均为互相包含关系。  
    

## 输出描述:
    
    
    $\hspace{15pt}$如果答案不存在，直接输出 $-1$ ；否则，在一行上输出一个长度为 $n$ 的 $\tt 01$ 串。  
      
    $\hspace{15pt}$如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

示例1 

## 输入
    
    
    4 2
    1 4 2 2 4
    2 3 1 1 1

## 输出
    
    
    0011

示例2 

## 输入
    
    
    4 2
    1 4 2 2 3
    2 3 1 1 1

## 输出
    
    
    -1


## 时空限制

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld
# 小红的01串（一）

## 题目描述

小红拿到了一个01串，她想知道这个01串有多少对相邻的字符满足，这两个字符是不同的？ 

## 输入描述:
    
    
    一个长度不超过100的字符串，仅由'0'和'1'组成。

## 输出描述:
    
    
    输出相邻的不同字符的对儿数。

示例1 

## 输入
    
    
    01011

## 输出
    
    
    3

## 说明
    
    
    有3对相邻的字符不相同。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 小红的01串（二）

## 题目描述

小红定义一个字符串是好串，当且仅当该字符串任意一对相邻字符都不同。  
现在小红拿到了一个01串，请你帮小红求出有多少个长度不小于2的连续子串是好串。  
  


## 输入描述:
    
    
    一个长度不超过200000的字符串，仅由'0'和'1'组成。  
    
    
      
    

## 输出描述:
    
    
    输出相邻字符均不同的连续子串数量。  
    
    
      
    

示例1 

## 输入
    
    
    01011

## 输出
    
    
    6

## 说明
    
    
    有2个"01"子串，1个"10"子串，1个"010"子串，1个"101"子串，1个"0101"子串。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 小红的01串（三）

## 题目描述

小红希望你构造一个由$a$个'0'、$b$个'1'组成的01串，该01串有恰好$k$对相邻的字符不同。

## 输入描述:
    
    
    第一行一个整数$t$，表示测试样例数。  
    接下来$t$行，每行三个整数$a,b,k$，用空格隔开。  
    $1\leq t\leq 10^4$  
    
    
    $0\leq a,b,k \leq 10^5$
    
    $a + b > 0$  
    
    
    保证所有测试样例的$a+b$的和不超过$5 \times 10^5$。

## 输出描述:
    
    
    对于每组测试样例，如果无解，请输出-1。  
    否则输出一个长度为$a+b$的01串。有多解时输出任意即可。

示例1 

## 输入
    
    
    2
    2 3 3
    1 1 1

## 输出
    
    
    01011
    01

## 说明
    
    
    对于第一组样例，输出11010也是可以的。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld
# 小红的01串（四）

## 题目描述

小红拿到了一个01串，她初始站在第一个字符。小红可以进行以下移动方式：  
1\. 花费$x$能量，移动到当前位置右边、离当前位置最近的，和当前字符相同的字符；  
2\. 花费$y$能量，移动到当前位置右边、离当前位置最近的，和当前字符不同的字符。  
  
小红想知道，她移动到最右端的最小花费是多少？

## 输入描述:
    
    
    第一行输入三个正整数$n,x,y$，用空格隔开，代表01串长度、第一种移动花费，第二种移动花费。  
    第二行输入一个长度为$n$的01串。  
    $1\leq n,x,y \leq 10^5$

## 输出描述:
    
    
    一个整数，代表花费的最小总能量。

示例1 

## 输入
    
    
    5 1 2
    01011

## 输出
    
    
    4

## 说明
    
    
    有两种方案均可：操作2+操作1+操作1 或者 操作1+操作2+操作1。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 小红的01串（五）

## 题目描述

小红拿到了一个01串，但其中有一些被'?'字符代替。  
小红希望将'?'替换成'0'或者'1'字符，使得该串表示的正整数是13的倍数。你能帮小红求出有多少种方案吗？  
由于答案过大，请对$10^9+7$取模

## 输入描述:
    
    
    一行仅由'0'、'1'、'?'三种字符组成的字符串。保证第一个字符是'1'。  
    字符串长度不超过200000。

## 输出描述:
    
    
    一个整数，代表最终合法方案数对$10^9+7$取模的答案。

示例1 

## 输入
    
    
    10?1

## 输出
    
    
    1

## 说明
    
    
    只有1001这一个合法解。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 小红的01串（六）

## 题目描述

小红定义一个字符串是好串，当且仅当该字符串任意一对相邻字符都不同。  
  
现在小红拿到了一个字符串，初始所有字符都是'0'，她希望你能维持以下操作：  
· 输入$1 \ l \ r$，将第$l$个字符到第$r$个字符修改为'1'。  
· 输入$2\ l\ r$ ，将第$l$个字符到第$r$个字符取反（即'1'变'0'，'0'变'1'）。  
· 输入$3 \ l \ r$ ，查询将第$l$个字符到第$r$个字符对应子串修改为好串的最小修改次数（每次可以修改一个字符）。

## 输入描述:
    
    
    第一行输入两个正整数$n,q$，代表字符串长度、操作次数。  
    接下来的$q$行，每行输入三个正整数$op,l,r$，分别代表操作类型和操作的区间。  
    $1\leq n \leq 10^9$  
    $1\leq q \leq 10^5$  
    $1\leq l \leq r \leq n$  
    保证至少有一次操作3。

## 输出描述:
    
    
    对于每次操作3输出一行，代表该次询问的答案。

示例1 

## 输入
    
    
    1000000000 2
    1 2 999999999
    3 1 10

## 输出
    
    
    4

## 说明
    
    
    查询的子串为"0111111111"，最少需要修改4次才能变成好串。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 构造A+B

## 题目描述

$\hspace{15pt}$对于给定的两个正整数 $n$ 和 $k$ ，是否能构造出 $k$ 对不同的正整数 $(x,y)$ ，使得 $x+y=n$ 。 

  


$\hspace{15pt}$我们认为两对正整数 $(x,y)$ 和 $(x',y')$ 是不同的，当且仅当 $x \neq x'$ 。 

## 输入描述:
    
    
    $\hspace{15pt}$第一行输入两个整数 $n,k \left( 1 \leqq n,k \leqq 10^5 \right)$ ，含义如题中所述。

## 输出描述:
    
    
    $\hspace{15pt}$如果存在满足题意的 $k$ 对不同正整数，在一行上输出 $\rm YES$ ；否则，直接输出 $\rm NO$ 。

示例1 

## 输入
    
    
    6 3

## 输出
    
    
    YES

## 说明
    
    
    $\hspace{15pt}$一共有如下五对合法答案：$(1,5)$ 、$(2,4)$ 、$(3,3)$ 、$(4,2)$ 和 $(5,1)$ 。

示例2 

## 输入
    
    
    7 666

## 输出
    
    
    NO


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld
# 宝石手串

## 题目描述

$\hspace{15pt}$小红有一个 $n$ 颗宝石构成的环形宝石手串，即第一颗和最后一颗宝石相连，其中第 $i$ 个宝石的属性为 $s_i$ ；若两个宝石的属性相同，那么这两个宝石会相互排斥，导致断开。  
$\hspace{15pt}$小红可以从手串中摘掉一些宝石，每次摘掉后，这个宝石左右的两个宝石会相接，手串依旧是环形。  


$\hspace{15pt}$小红想要破坏这个手串。她想要知道，最少还需要摘掉多少个宝石才会导致手串断开。特别的，当手串上剩余的宝石数量恰好为 $2$ 而依旧没能断开时，视为破坏失败，直接输出 $-1$ 。 

## 输入描述:
    
    
    $\hspace{15pt}$每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\leqq T\leqq 100\right)$ 代表数据组数，每组测试数据描述如下：  
    
    
      
    
    
    $\hspace{15pt}$第一行输入一个整数 $n \left( 2 \leqq n \leqq 10^5 \right)$ 代表手串初始的宝石数量。
    
    $\hspace{15pt}$第二行输入一个长度为 $n$ 、仅由小写字母构成的字符串，代表手串上每个宝石的属性。
    
      
    
    
    $\hspace{15pt}$除此之外，保证单个测试文件的 $n$ 之和不超过 $10^5$ 。  
    

## 输出描述:
    
    
    $\hspace{15pt}$对于每一组测试数据，如果手环无法破坏，直接输出 $-1$ ；否则，在一行上输出一个整数，代表手串断开需要的最少操作次数。

示例1 

## 输入
    
    
    2
    2
    ac
    3
    aac

## 输出
    
    
    -1
    0


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
# 最小循环节

## 题目描述

$\hspace{15pt}$给定一个长度为 $n$ 、由大小写字母混合构成的字符串 $s$，你可以无限次的往字符串的任何地方插入任意字符。求新字符串 $s$ 的 _最小循环节_ 。 

  


$\hspace{15pt}$对于字符串 $b$ ，找到最短长度的子串 $a$ ，使得字符串 $b$ 是由子串 $a$ 拼接若干次得到的，即 $b=aa \cdots a$ 。这里的子串 $a$ 的长度即为字符串 $b$ 的 _最小循环节_ 。  


## 输入描述:
    
    
    $\hspace{15pt}$在一行上输入一个长度不超过 $10^5$ 、由大小写字母混合构成的字符串 $s$ ，代表初始字符串。

## 输出描述:
    
    
    $\hspace{15pt}$在一行上输出一个整数，代表字符串 $s$ 的最小循环节的长度。

示例1 

## 输入
    
    
    abcabcD

## 输出
    
    
    4

## 说明
    
    
    $\hspace{15pt}$在字符串 $\texttt{"abcDabcD"}$ 中，最小循环节为 $\texttt{"abcD"}$ ，其长度为 $4$ 。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
# 气球谜题

## 题目描述

$\hspace{15pt}$对于给定的 $n$ 个气球，摆放成一排，颜色仅为红、黄、蓝中的一种。小红想要让颜色相同的气球连续的摆放在一起，为了达成这个目标，她需要将气球重新染色。第 $i$ 个气球重新染成任意的颜色均需要 $t_i$ 秒，询问需要消耗的最少时间是多少呢。

## 输入描述:
    
    
    $\hspace{15pt}$第一行输入一个整数 $n \left( 1\leqq n \leqq 2 \times 10^5 \right)$ 代表气球数量。  
    $\hspace{15pt}$第二行输入一个长度为 $n$ 的、仅由 $0,1,2$ 构成的字符串代表气球的初始颜色。其中，$0,1,2$ 分别代表初始颜色为红、黄、蓝。  
    $\hspace{15pt}$第三行输入 $n$ 个整数 $t_1,t_2,\dots,t_n \left( 1 \leqq t_i \leqq 10^7 \right)$ 代表气球重新染色需要的时间。

## 输出描述:
    
    
    $\hspace{15pt}$在一行上输出一个整数，代表最少需要的染色时间。

示例1 

## 输入
    
    
    5
    00000
    1 2 3 4 5

## 输出
    
    
    0

## 说明
    
    
    $\hspace{15pt}$由于初始时全部气球颜色都是一样的，所以不需要重新进行染色。

示例2 

## 输入
    
    
    6
    210102
    1 1 4 5 1 4

## 输出
    
    
    3

## 说明
    
    
    $\hspace{15pt}$其中一种最优的染色方案是将气球染色为 $\texttt{"000112"}$ ，花费 $3$ 。

示例3 

## 输入
    
    
    6
    001012
    1 1 4 5 1 4

## 输出
    
    
    3

## 说明
    
    
    $\hspace{15pt}$其中一种最优的染色方案是将气球染色为 $\texttt{"111002"}$ ，花费 $3$ 。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 三角谜题

## 题目描述

$\hspace{15pt}$对于给定的 $n$ 种长度的棍子，第 $i$ 种棍子的长度为 $l_i$ ，有 $a_i$ 根。从中任选三根，能组成的等腰三角形的面积最大值为多少？  
$\hspace{15pt}$如果无法组成等腰三角形，则直接输出 $-1$ 。

## 输入描述:
    
    
    $\hspace{15pt}$每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\leqq T\leqq 10^6 \right)$ 代表数据组数，每组测试数据描述如下：  
      
    $\hspace{15pt}$第一行输入一个整数 $n \left( 1\leqq n \leqq 10^6 \right)$ 代表棍子的种类。  
    $\hspace{15pt}$此后 $n$ 行，第 $i$ 行输入两个整数 $l_i, a_i \left(1 \leqq l_i, a_i \leqq 10^9 \right)$ 代表第 $i$ 种棍子的长度和数量。  
      
    $\hspace{15pt}$除此之外，保证单个测试文件的 $n$ 之和不超过 $10^6$ 。

## 输出描述:
    
    
    $\hspace{15pt}$在一行上输出一个实数，代表组成的最大等腰三角形的面积。如果无法组成等腰三角形，则直接输出 $-1$ 。  
      
    $\hspace{15pt}$由于实数的计算存在误差，当误差的量级不超过 $10^{-6}$ 时，您的答案都将被接受。具体来说，设您的答案为 $a$ ，标准答案为 $b$ ，当且仅当 $\frac{|a-b|}{\max(1,|b|)}\leqq 10^{-6}$ 时，您的答案将被接受。

示例1 

## 输入
    
    
    2
    3
    3 3
    2 1
    3 1
    2
    1 2
    12 1

## 输出
    
    
    3.89711431702997391060
    -1

## 说明
    
    
    $\hspace{15pt}$对于第一组测试数据，可以构造 $2$ 为底、$3$ 为腰的三角形，面积 $\approx 2.83$ ；也可以构造 $3$ 为底、$3$ 为腰的三角形，面积 $\approx 3.90$ 。显然，后者更大。

## 备注:
    
    
    $\hspace{15pt}$本题数据量较大，我们建议您使用较快的读入方式。


## 时空限制

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld
# 变化的数组

## 题目描述

$\hspace{15pt}$对于给定的长度为 $n$ 的数组 $\\{a_1,a_2,\dots,a_n\\}$ 和一个整数 $m$ ，保证全部非负。你需要执行 $k$ 次操作，每一次操作如下：  
$\hspace{22.5pt}\bullet\ $对数组中的每一个元素 $a_i$ ，投掷一次硬币，若硬币为正则将这个元素修改为 $a_i + (a_i \operatorname{and} m)$ ；反之，则不操作；  


$\hspace{15pt}$在全部 $k$ 次操作完成后，求解数组元素和的期望。 

  


$\hspace{15pt}$在本题中，$\operatorname{and}$ 运算即按位与运算。如果您需要更多位运算相关的知识，可以参考 [**OI-Wiki上的相关章节**](https://oi-wiki.org/math/bit/#%E4%B8%8E%E6%88%96%E5%BC%82%E6%88%96) 。 

## 输入描述:
    
    
    $\hspace{15pt}$第一行输入三个整数 $n,m,k \left( 1\leqq n \leqq 10^5;\ 1 \leqq m, k \leqq 10^9 \right)$ 代表数组中的元素数量、修改公式中的定值、操作次数。  
    $\hspace{15pt}$第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n \left( 0 \leqq a_i \leqq 10^9 \right)$ 代表数组元素。

## 输出描述:
    
    
    $\hspace{15pt}$在一行上输出一个整数，代表 $k$ 次操作完成后数组元素和的期望。  
      
    $\hspace{15pt}$可以证明答案可以表示为一个不可约分数 $\frac{p}{q}$ ，为了避免精度问题，请直接输出整数 $\left(p \cdot q^{-1} \bmod M\right)$ 作为答案，其中 $M = (10^9 + 7)$ ，$q^{-1}$ 是满足 $q\times q^{-1}  \equiv 1 \pmod{M}$ 的整数。

示例1 

## 输入
    
    
    2 6 1
    3 5

## 输出
    
    
    11

## 说明
    
    
    $\hspace{15pt}$全过程模拟如下：  
    $\hspace{22.5pt}\bullet\ $ $\frac{1}{4}$ 的概率第一个元素硬币为正、第二个元素硬币也为正，答案为 $\frac{1}{4} \times \big(3 + (3 \operatorname{and} m) + 5 + (5 \operatorname{and} m) \big) =\frac{14}{4}$ ；  
    $\hspace{22.5pt}\bullet\ $ $\frac{1}{4}$ 的概率第一个元素硬币为正、第二个元素硬币为反，答案为 $\frac{1}{4} \times \big(3 + (3 \operatorname{and} m) + 5 \big) =\frac{10}{4}$ ；  
    $\hspace{22.5pt}\bullet\ $ $\frac{1}{4}$ 的概率第一个元素硬币为反、第二个元素硬币为正，答案为 $\frac{1}{4} \times \big(3 + 5 + (5 \operatorname{and} m) \big) =3$ ；  
    $\hspace{22.5pt}\bullet\ $ $\frac{1}{4}$ 的概率第一个元素硬币为反、第二个元素硬币也为反，答案为 $\frac{1}{4} \times \big(3 + 5\big) =2$ ；  
    $\hspace{15pt}$综上，期望为 $11$ 。

示例2 

## 输入
    
    
    3 1 4
    1 1 1

## 输出
    
    
    312500008


## 时空限制

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld