yl-9/probench huggingface dataset:
# Letter Song ~ 致十年后的我们

## 题目描述

> 这个月，牛客科技创立十周年啦！  
>  2014~2024，回望这十年时光，每个人一定都有无数想要感慨，想要抱怨，想要倾诉，想要怀念的事情。  
>  十年前的你有对自己说过什么吗？  
>  你想对十年后的自己说点什么吗？ 

$~~~~~~$已知你在 $\sf Y$ 年 $\sf M$ 月 $\sf D$ 日向十年后的自己发送了一条消息；请你精确的计算出，哪一天的自己会收到这条消息。  


> 10年後の私へ 今がもし幸せなら  
>  あの日の私のこと 思い出してくれますか  
>  そこにはつらいことに 泣いた私がいるけど  
>  その涙を優しく 思い出に変えてください 

## 输入描述:
    
    
    $~~~~~~$在一行上输入一个 $\textsf{YYYY-MM-DD} \left( 2000 \le {\sf Y} \le 2024;\ 1 \le {\sf M} \le 12;\ 1 \le {\sf D} \le 28 \right)$ 模式的字符串代表日期。保证时间格式满足 $\textsf{ISO8601}$ 规定的日历日期表示法。这也意味着您无需考虑平闰年对答案的影响。

## 输出描述:
    
    
    $~~~~~~$在一行上输出一个 $\textsf{YYYY-MM-DD}$ 模式的字符串代表日期。

示例1 

## 输入
    
    
    2014-09-05

## 输出
    
    
    2024-09-05


## 时空限制

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

Tags: 字符串, 模拟
Difficulty: 400
# 简单图形问题 - 0123

## 题目描述

$\,\,\,\,\,\,\,\,\,\,$对于给定的未知多边形的面积，请你判断这是一个以整数为边长的正方形、或是以整数为边长的等边三角形、或是两者均是、或是两者均不是。

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$每个测试文件均包含多组测试数据。第一行输入一个整数 $T\ (1\le T\le 10^5)$ 代表数据组数，每组测试数据描述如下：
    
      
    
    
    $\,\,\,\,\,\,\,\,\,\,$在一行上输入一个整数 $s\ (1 \le s \le 10^9)$ 代表未知多边形的面积。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$对于每一组测试数据，在一行上输出一个整数，代表未知多边形的种类。其中 $0$ 代表正方形、$1$ 代表等边三角形、$2$ 代表两者都有可能、$3$ 代表两者均不可能。

示例1 

## 输入
    
    
    2
    25
    18

## 输出
    
    
    0
    3

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,\,$对于第一个样例，是边长为 $5$ 的正方形。


## 时空限制

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

Tags: 计算几何
Difficulty: 400
# 小红的机器人构造 - Ⅰ+Ⅱ+Ⅲ

## 题目描述

$~~~~~~$在无限大的网格平面上，我们使用 $(x,y)$ 表示网格中第 $x$ 行第 $y$ 列的单元格。  
$~~~~~~$小红有一只笨笨机器人初始位于 $(0,0)$ 单元格，她会向机器人下达 $n$ 个指令，机器人跟随指令上下左右移动。指令字符串由 $\texttt{U,D,L,R}$ 四个字符混合构成，以 $1$ 作为初始下标，形式化写作 $s_1s_2 \cdots s_n$ 。具体的，假设 $t$ 时刻机器人位于 $(i,j)$ 单元格，若指令字符串的第 $t+1$ 个字符存在：  
$~~~~~~~~~$$\bullet\ $若 $s_{t+1} = \tt U$ ，则第 $t+1$ 时刻机器人位于 $(i + 1, j)$ ；  
$~~~~~~~~~$$\bullet\ $若 $s_{t+1} = \tt D$ ，则第 $t+1$ 时刻机器人位于 $(i - 1, j)$ ；  
$~~~~~~~~~$$\bullet\ $若 $s_{t+1} = \tt L$ ，则第 $t+1$ 时刻机器人位于 $(i, j - 1)$ ；  
$~~~~~~~~~$$\bullet\ $若 $s_{t+1} = \tt R$ ，则第 $t+1$ 时刻机器人位于 $(i, j + 1)$ ；  


$~~~~~~$给出指令字符串，询问，能否删除部分指令（保持其余指令的相对位置不变），使得机器人最终位于 $(x,y)$ 。如果可以，计算有多少种不同的删除方案（删除不同下标视为不同方案），并输出其中任意一种。 

## 输入描述:
    
    
    $~~~~~~$每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\le T\le 6\right)$ 代表数据组数，每组测试数据描述如下：  
    $~~~~~~$第一行输入三个整数 $n,x,y \left(1 \le n < 10^5;\ -n \le x,y \le n \right)$ 代表指令数量、终点位置。  
    $~~~~~~$第二行输入一个长度为 $n$ 、仅由 $\texttt{U,D,L,R}$ 四个字符混合构成的字符串 $s$ ，代表小红的指令字符串。

## 输出描述:
    
    
    $~~~~~~$**对于子问题Ⅰ，输出规范如下，你至多可以从中获取** $\sf 40$**分：**  
     $~~~~~~$对于每一组测试数据，如果能够通过删除部分指令使得机器人最终位于终点 $(x,y)$ ，输出 $\rm YES$ 。  
    $~~~~~~$否则，直接输出 $\rm NO$ 。  
      
    $~~~~~~$**对于子问题Ⅱ，输出规范如下，你至多可以从中获取** $\sf 80$**分：**  
     $~~~~~~$对于每一组测试数据，如果能够通过删除部分指令使得机器人最终位于终点 $(x,y)$ ，在一行上输出 $\rm YES$ ，随后在同一行输出一个字符串，代表删除后的新指令串。彼此间使用单个空格间隔。  
    $~~~~~~$否则，直接输出 $\rm NO$ 。  
      
    $~~~~~~$******对于子问题Ⅲ，输出规范如下，你至多可以从中获取** $\sf 240$**分：**  
     $~~~~~~$对于每一组测试数据，如果能够通过删除部分指令使得机器人最终位于终点 $(x,y)$ ，在一行上输出 $\rm YES$ ，随后在同一行输出一个字符串，代表删除后的新指令串；最后在同一行输出一个整数，代表符合条件的不同删除方案的数量，由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。彼此间使用单个空格间隔。  
    $~~~~~~$否则，直接输出 $\rm NO$ 。  
      
    
    
    $~~~~~~$如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。
    
    $~~~~~~$本题采用类捆绑测试的 $\textsf{Special Judge}$ 检查答案，通过空格分隔输出并依次检查答案，请你严格依照输出描述进行输出，输出多余内容、未按照子问题输出格式输出等行为，有可能会导致输出格式错误。如果你有任何疑问，欢迎在提问区向我们提出。  
    

示例1 

## 输入
    
    
    3
    4 2 2
    LRDU
    4 0 0
    LRDU
    6 2 -3
    LLULLU

## 输出
    
    
    NO
    YES  4
    YES LULLU 4

## 说明
    
    
    $~~~~~~$对于第一个样例，无论怎么删除，机器人都无法到达到达终点。  
    $~~~~~~$对于第二个样例，将指令串全部删除是其中一种方案，与此同时，$\texttt{"LR"}$ 、$\texttt{"DU"}$ 和 $\texttt{"LRDU"}$ 也是合法的方案，所以一共有 $4$ 种合法方案。  
    $~~~~~~$对于第三个样例，我们使用下划线 ![\\texttt{_}](https://hr.nowcoder.com/equation?tex=%5Ctexttt%7B_%7D) 来填充被删除的位置，合法方案有：![\\texttt{](https://hr.nowcoder.com/equation?tex=%5Ctexttt%7B%22_LULLU%22%7D) 、![\\texttt{](https://hr.nowcoder.com/equation?tex=%5Ctexttt%7B%22L_ULLU%22%7D) 、![\\texttt{](https://hr.nowcoder.com/equation?tex=%5Ctexttt%7B%22LLU_LU%22%7D) 和 ![\\texttt{](https://hr.nowcoder.com/equation?tex=%5Ctexttt%7B%22LLUL_U%22%7D) 。


## 时空限制

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

Tags: 组合数学, 贪心, 模拟
Difficulty: 1400
# 小红的差值构造 - easy+hard+extreme

## 题目描述

$~~~~~~$小红有一个长度为 $n$ 的数组 $\\{1,2,\dots,n\\}$ 和一个整数 $l$ ，她想找到这样两个整数 $x$ 和 $y$ ，满足 $y - x = l$ ，记 $f_i=\min\big\\{|a_i - x|, |a_i - y| \big\\}$ ，使得 $f_1+f_2+\dots+f_n$ 最小。  
$~~~~~~$你需要输出满足条件的 $x$ 和 $y$ ，以及这个最小值。

## 输入描述:
    
    
    $~~~~~~$每个测试文件均包含多组测试数据。
    
      
    
    
    $~~~~~~$**对于简单版本，范围如下，你至多可以从中获取** $\sf 70$**分**（含样例）** ：**  
    $~~~~~~$第一行输入一个整数 $T\left(1\le T\le 5\right)$ 代表数据组数，每组测试数据描述如下：  
    $~~~~~~$在一行上输入两个整数 $n,l \left( 1 \le n,l \le 20 \right)$ 代表数组长度、构造限制。  
    
    
      
    $~~~~~~$**对于困难版本，范围如下，你至多可以从中获取** $\sf 163.33$**分（含样例）：**  
     $~~~~~~$第一行输入一个整数 $T\left(1\le T\le 5\right)$ 代表数据组数，每组测试数据描述如下：  
    $~~~~~~$在一行上输入两个整数 $n,l \left( 1 \le n,l \le 2 \times 10^6 \right)$ 代表数组长度、构造限制。  
      
    $~~~~~~$**对于极限版本，范围如下，你至多可以从中获取** $\sf 350$**分**（含样例）** ：**  
    $~~~~~~$第一行输入一个整数 $T\left(1\le T\le 2 \times 10^5\right)$ 代表数据组数，每组测试数据描述如下：  
    $~~~~~~$在一行上输入两个整数 $n,l \left( 1 \le n,l \le 2 \times 10^6 \right)$ 代表数组长度、构造限制。

## 输出描述:
    
    
    $~~~~~~$对于每一组测试数据，在一行上输出三个整数，代表满足条件的 $x$ 和 $y$ ，以及最小的 $\sum f$ 。  
      
    
    
    $~~~~~~$如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。
    
    $~~~~~~$在几乎全部的情况下，$\sf PyPy$ 的运行速度优于 $\sf Python$ ，我们建议您选择对应版本的 $\sf PyPy$ 进行提交、而不是 $\sf Python$ 。  
    

示例1 

## 输入
    
    
    3
    3 1
    3 1
    3 5

## 输出
    
    
    2 3 1
    1 2 1
    -3 2 2

## 说明
    
    
    $~~~~~~$对于第一组测试样例，$\begin{cases}
    f_1= \min \big\{ |1 - 2|, |1 - 3| \big\} = 1
    \\
    f_2=  \min \big\{ |2 - 2|, |2 - 3| \big\} = 0
    \\
    f_3=  \min \big\{ |3 - 2|, |3 - 3| \big\} = 0 
    \end{cases}$ ，可以证明 $\sum f = 1$ 是最小的答案。


## 时空限制

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

Tags: 分治, 三分, 数论
Difficulty: 1700
# 困难数学题

## 题目描述

$\,\,\,\,\,\,\,\,\,$小歪正在计算数学题：$y=x \operatorname{xor} x \operatorname{xor} x\operatorname{xor} x$ 。多难啊，帮帮小歪吧。 

  


$\,\,\,\,\,\,\,\,\,$在这里，$\rm xor$ 表示位运算中的按位异或运算。

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,$第一行上输入一个整数 $x \left(0\le x \le 500 \right)$ 。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,$第一行上输出一个整数 $y$ 代表方程答案。

示例1 

## 输入
    
    
    0

## 输出
    
    
    0

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,$我们都知道，异或运算（ $\operatorname{xor}$ ）的口诀就是”不同出一，相同出零“。所以  $0 \operatorname{xor} 0 \operatorname{xor} 0\operatorname{xor} 0=0$ 。


## 时空限制

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

Difficulty: 400
# 构造序列

## 题目描述

$\,\,\,\,\,\,\,\,\,$给你 $n$ 个正数和 $m$ 个负数，请你使用这些数字，构造一个序列。  
$\,\,\,\,\,\,\,\,\,$序列需要满足：正数不能和正数相邻，负数不能和负数相邻。  
$\,\,\,\,\,\,\,\,\,$那么，最多能构造多长的序列？

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,$第一行输入两个整数 $n,m\ (\ 1 \leq n,m \leq 10^9\ )$ 代表正数数量、负数数量。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,$在一行上输出一个整数，代表能构造的最长序列的长度。

示例1 

## 输入
    
    
    7 6

## 输出
    
    
    13


## 时空限制

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

Difficulty: 400
# 连点成线

## 题目描述

$~~~~~~$小红有一个 $n \times n$ 大小的格子棋盘，我们使用 $(i,j)$ 表示棋盘中从上往下数第 $i$ 行和从左往右数第 $j$ 列的单元格。棋盘上有 $m$ 个棋子，第 $i$ 个棋子的坐标是 $(x_i,y_i)$ 。  
$~~~~~~$对于一对棋子 $i$ 和 $j$ ，如果满足 $x_i=x_j$ 或者 $y_i=y_j$ ，则两个棋子之间可以连线。  
$~~~~~~$小红有点无聊，于是她把能连的线都连上了。现在，她想知道，最长的那条线，长度是多少。  
$~~~~~~$特别地，如果连线数量为 $0$ ，则输出 $0$ 。

## 输入描述:
    
    
    $~~~~~~$第一行输入两个整数 $n\ (\ 1 \leq n \leq 10^5\ )$ 和 $m\ \big(1 \leq m \leq \min\{10^5,n^2\}\big)$ 代表棋盘大小、棋子数量。  
    $~~~~~~$随后 $m$ 行，每行输入两个整数 $x_i,y_i\ (\ 1 \leq x_i,y_i \leq n\ )$ 代表第 $i$ 个棋子的坐标。**保证不会出现重复的坐标。**

## 输出描述:
    
    
    $~~~~~~$输出一个整数，代表最长连线的长度。

示例1 

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

## 输出
    
    
    4

## 说明
    
    
    $~~~~~~$如下图所示，$(1,1)$ 和 $(1,5)$ 的连线是最长的（使用绿色标注），长度为 $4$ 。
    
    $~~~~~~$![](https://uploadfiles.nowcoder.com/images/20240909/0_1725868159861/39A56265CB8C59E8475B94A940A518AB)  
    

示例2 

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

## 输出
    
    
    0

## 说明
    
    
    $~~~~~~$这是一个经典的 $8$ 皇后棋盘，任何行和列都只有一颗棋子。无法连线，答案为 $0$ 。
    
    $~~~~~~$![](https://uploadfiles.nowcoder.com/images/20240909/0_1725868206215/DFA5A702A6C91035FAF9DA6E50039843)


## 时空限制

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

Difficulty: 700
# 我们N个真是太厉害了

## 题目描述

$~~~~~~$这天，$n$ 位小朋友聚在一起吹牛，他们每个人手里都有一定数量的小星星，为了方便统计，我们使用 $a_1,a_2,\dots,a_n$ 来表示。  
$~~~~~~$小小歪吹牛到，从我们几个人中挑出几个来，手里的小星星数量全部加起来，可以表示出 $n$ 以内的任意一个正整数！  
$~~~~~~$小小龙认为小歪错了，但是他是小朋友，他不会计算。  
$~~~~~~$所以小小龙来求助你，他想让你找到最小的整数证明小小歪是错误的。

## 输入描述:
    
    
    $~~~~~~$每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\le T\le 10^5\right)$ 代表数据组数，每组测试数据描述如下：  
      
    $~~~~~~$第一行输入一个整数 $n \left( 2 \le n \le 10^5 \right)$ 代表小朋友数量。  
    $~~~~~~$第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n\left( 1 \le a_i \le 10^6 \right)$ 代表每位小朋友手中的小星星数量。  
      
    $~~~~~~$除此之外，保证所有的 $n$ 之和不超过 $2 \times 10^5$ 。

## 输出描述:
    
    
    $~~~~~~$对于每一组测试数据，如果小小歪没有在吹牛，在一行上输出 $\sf Cool!$ 否则，在一行上输出一个最小的整数，代表从 $n$ 位小朋友中任意挑选几位小朋友，他们手中的小星星全部加起来无法构成的最小数字。

示例1 

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

## 输出
    
    
    Cool!
    2


## 时空限制

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

Difficulty: 1200
# 折返跑

## 题目描述

> $\,\,\,\,\,\,\,\,\,$折返跑是一种跑步运动形式，运动者从一侧的杆子出发，跑向另一侧的杆子，绕过杆子跑回起点，绕过起点的杆子再跑向另一侧，不断重复这一过程。这种运动形式有助于高效利用空间，运动者可以在有限的区域内进行无限的锻炼。  
>  $\,\,\,\,\,\,\,\,\,$了解了折返跑的运动方法后，$\sf Zaoly$不屑道：“哼，杆子不动的折返跑没有灵魂，杆子不断移动的才有意思！”说干就干，他立即进行了一场移动杆折返跑运动。 

$\,\,\,\,\,\,\,\,\,$上体育课了！今天的项目是折返跑，笔直的跑道可以看作是一条数轴。跑道上有 $n$ 个点位，其中，老师在 $1$ 点和 $n$ 点处各放了两根杆子，称为左杆和右杆，作为折返跑的折返点。  
$\,\,\,\,\,\,\,\,\,$老师规定，今天一共需要跑 $m$ 趟。我们认为，从一根杆子开始，跑到另一根杆子结束为一趟，显然，一共需要进行 $m-1$ 次折返。$\sf Zaoly$偶然发现，杆子是可推动的，所以他有了一个大胆的想法——  
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\bullet\,$每次跑至右杆折返后，都需要把右杆向左推动一段距离（大于 $0$），但仍保证右杆位于整数点，且在左杆的右边（不能与左杆重合）；  
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\bullet\,$每次跑至左杆折返后，都需要把左杆向右推动一段距离（大于 $0$），但仍保证左杆位于整数点，且在右杆的左边（不能与右杆重合）；  
$\,\,\,\,\,\,\,\,\,$现在，给出整数 $n$ 和 $m$ 的值，请问$\sf Zaoly$一共有多少种不同的推杆方法？由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。注意，每次折返时都需要推杆，如果某一轮无法推动，则这一轮推杆非法。

## 输入描述:
    
    
    $~~~~~~$每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\le T\le 10^4\right)$ 代表数据组数，每组测试数据描述如下：  
    $~~~~~~$对于每一组测试数据，输入两个整数 $​n,m \left(1 \leq m < n \leq 10^6 \right)$ 代表点位的数量、折返跑的趟数。

## 输出描述:
    
    
    $~~~~~~$对于每组数据，在一行上输出一个整数代表合法的推杆方法种类数。由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。

示例1 

## 输入
    
    
    3
    4 3
    5 3
    100 1

## 输出
    
    
    1
    3
    1

## 说明
    
    
    $~~~~~~$对于第一组测试数据，有且仅有唯一的推杆方法：  
    
    
    $~~~~~~~~~$$\bullet\ $在第一次折返时（位于右杆），将右杆向左推一个点位；随后在第二次折返时（位于左杆），将左杆向右推一个点位；
    
      
    
    
    $~~~~~~$对于第二组测试数据，有以下三种推杆方法：  
    $~~~~~~~~~$$\bullet\ $在第一次折返时（位于右杆），将右杆向左推一个点位；随后在第二次折返时（位于左杆），将左杆向右推一个点位；  
    $~~~~~~~~~$$\bullet\ $在第一次折返时，将右杆向左推两个点位；随后在第二次折返时，将左杆向右推一个点位；  
    $~~~~~~~~~$$\bullet\ $在第一次折返时，将右杆向左推一个点位；随后在第二次折返时，将左杆向右推两个点位。  
    
    
      
    
    
    $~~~~~~$对于第三组测试数据，由于只跑一趟，没有折返，所以没有推杆，这也算作一种推杆方法。  
    


## 时空限制

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

Difficulty: 1500
# 口吃

## 题目描述

$~~~~~~$$\sf Zaoly$要讲一句话，这句话有 $n$ 个字，他要一个字一个字讲出来。奈何 $\sf Zaoly$ 口吃：  
$~~~~~~~~~$$\bullet\ $讲到第 $1$ 个字时，下一个要讲的字有 $\frac {a_1} {a_1 + b_1}$ 的概率前进到第 $2$ 个字，有 $\frac {b_1} {a_1 + b_1}$ 的概率仍是第 $1$ 个字。  
$~~~~~~~~~$$\bullet\ $讲到第 $i$（$2 \leq i \leq {n - 1}$）个字时，下一个要讲的字有 $\frac {a_i^2} {a_i^2 + 2 a_i \cdot b_i + b_i^2}$ 的概率前进到第 $i + 1$ 个字，有 $\frac {2 a_i \cdot b_i} {a_i^2 + 2 a_i \cdot b_i + b_i^2}$ 的概率仍是第 $i$ 个字，有 $\frac {b_i^2} {a_i^2 + 2 a_i \cdot b_i + b_i^2}$ 的概率倒退到第 $i - 1$ 个字。  
$~~~~~~~~~$$\bullet\ $讲到第 $n$ 个字时，讲话完毕，停止讲话。  
$~~~~~~$直到讲话完毕，$\sf Zaoly$总共讲出的字数的期望是多少？

## 输入描述:
    
    
    $~~~~~~$第一行输入一个整数 $n\ (2 \leq n \leq 10^5)$，表示这句话有 $n$ 个字。  
    $~~~~~~$第二行输入 $n - 1$ 个数 $a_1,a_2,\dots,a_{n - 1}\ (1  \leq  a_i  \leq 10^9)$ 表示数组。  
    
    
    $~~~~~~$第三行输入 $n - 1$ 个数 $b_1,b_2,\dots,b_{n - 1}\ (1 \leq b_i \leq 10^9)$ 表示数组。
    
    $~~~~~~$保证对于所有的 $1 \leq i \leq n - 1$，都满足 $a_i + b_i \neq 10^9 + 7$。  
    

## 输出描述:
    
    
    $~~~~~~$输出总共讲出的字数的期望。  
      
    $~~~~~~$可以证明答案可以表示为一个不可约分数 $\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
    1
    1

## 输出
    
    
    3

## 说明
    
    
    $~~~~~~$说完第一个字后，有 $1 / 2$ 的概率直接前进到下一个字，有 $1 / 4$ 的概率多讲一个字，有 $1 / 8$ 的概率多讲两个字......  
    $~~~~~~$说出总字数的期望为 $1 + \frac{1}{2} \times 1 + \frac1 4 \times 2+ \frac1 8 \times 3 + \frac1 {16} \times 4 + \cdots = 3$

示例2 

## 输入
    
    
    3
    1 1
    1 1

## 输出
    
    
    9

示例3 

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

## 输出
    
    
    800000096


## 时空限制

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

Difficulty: 2000
# TD

## 题目描述

$\,\,\,\,\,\,\,\,\,$周赛 $\textsf{Round59}$ 马上就要开始了，清楚姐姐正在群里发送比赛信息。大家都在发送 $\textsf{TD}$（退订的缩写），清楚姐姐很生气，她统计了发送 $\textsf{TD}$ 的人数 $n$ 和本次周赛的报名参赛人数 $m$ ，想要知道——如果发送了 $\textsf{TD}$ 的人都已经报名了本次周赛，那么随便挑选一个报名了周赛的人，他发了 $\textsf{TD}$ 的概率是多少。

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,$在一行上输入两个整数 $n,m \left(1\le n\le m \le 10^5\right)$ 代表发送 $\textsf{TD}$ 的人数、本次周赛的报名参赛人数。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,$在一行上输出一个实数，代表随机挑选出一名选手是发送 $\textsf{TD}$ 的坏蛋的概率。  
      
    $\,\,\,\,\,\,\,\,\,$由于实数存在误差，如果误差的级别不超过 $10^{-6}$ ，您的答案将被接受。具体来说，设您的答案为 $a$ ，标准答案为 $b$ ，当且仅当 $\frac{|a-b|}{\max(1,|b|)}\le 10^{-6}$ 时，您的答案将被接受。

示例1 

## 输入
    
    
    114 1514

## 输出
    
    
    0.075297225892


## 时空限制

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

Tags: 模拟
Difficulty: 400
# 你好，这里是牛客竞赛

## 题目描述

$\,\,\,\,\,\,\,\,\,$经常使用牛客的同学都知道，牛客的主站前缀是 $\texttt{https://www.nowcoder.com}$ ，而牛客竞赛的前缀是 $\texttt{https://ac.nowcoder.com}$ ，而有的时候，我们也会简写去除 $\texttt{https://}$ ，改为 $\texttt{www.nowcoder.com}$ 和 $\texttt{ac.nowcoder.com}$ 。  
$\,\,\,\,\,\,\,\,\,$现在，对于给出的网站，你需要判断它是牛客主站还是牛客竞赛，还是其他网站。

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,$每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\le T\le 1000\right)$ 代表数据组数，每组测试数据描述如下：  
      
    $\,\,\,\,\,\,\,\,\,$在一行上输入一个长度为 $|s|\ (1 \le |s| \le 100)$ 、且由大小写字母、数字、 $\texttt{:}$ 和 $\texttt{/}$ 混合构成的字符串 $s$ ，代表待确认的网址。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,$对于每一组测试数据，如果是牛客主站，在一行上输出 $\rm Nowcoder$ ；如果是竞赛站，在一行上输出 $\rm Ac$ ；否则，直接输出 $\rm No$ 。

示例1 

## 输入
    
    
    5
    https://ac.nowcoder.com/acm/contest/88848
    https://www.nowcoder.com/users/214360960
    ac.nowcoder.com/damedame
    www.nowcoder.com
    www.ac.nowcoder.com

## 输出
    
    
    Ac
    Nowcoder
    Ac
    Nowcoder
    No


## 时空限制

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

Tags: 字符串, 模拟
Difficulty: 500
# 逆序数

## 题目描述

$\,\,\,\,\,\,\,\,\,$已知某个 _排列_ $\\{x_1, x_2, \dots, x_n\\}$ 的 _**逆序数**_ 为 $k$ ，请你输出 $\\{x_n, x_{n-1}, \dots, x_1\\}$ 的逆序数。如果有多个不同的答案，按照任意顺序依次输出。  
  
$\,\,\,\,\,\,\,\,\,$长度为 $n$ 的 _排列_ 是由 $1 \sim n$ 这 $n$ 个整数、按任意顺序组成的数组，每个整数恰好出现一次。例如，$\\{2,3,1,5,4\\}$ 是一个排列，但 $\\{1,2,2\\}$ 不是一个排列（数组中的 $2$ 出现了两次），$\\{1,3,4\\}$ 也不是一个排列（长度为 $3$ 但数组中有 $4$ ）。  
$\,\,\,\,\,\,\,\,\,$_**逆序数**_ 指序列中逆序对的数量，即有多少对 $(i, j)$ 满足 $i < j$ 且 $x_i > x_j$ 。

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,$在一行上输入两个整数$n, k \left(1 \leq n \leq 10^5;\ 0 \leq k \leq \frac{n \times (n - 1)}{2} \right)$ 代表排列的长度和原始排列的逆序数。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,$在一行上输出若干个不同的整数，代表将原始排列逆序后的排列的逆序数。
    
      
    
    
    $\,\,\,\,\,\,\,\,\,$如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。  
    

示例1 

## 输入
    
    
    3 1

## 输出
    
    
    2

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,$原始排列可以是 $\{1, 3, 2\}$ ，逆序数为 $1$ ，满足题意。逆序后的排列为 $\{2, 3, 1\}$ ，逆序数为 $2$ ；
    
    $\,\,\,\,\,\,\,\,\,$原始排列也可以是 $\{2,1,3\}$ ，逆序数为 $1$ ，满足题意。逆序后的排列为 $\{3,1,2\}$ ，逆序数为 $2$ ；
    
    $\,\,\,\,\,\,\,\,\,$没有更多的原始排列，去重后只需要输出一个 $2$ 。  
    


## 时空限制

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

Tags: 数学
Difficulty: 700
# 构造mex

## 题目描述

$~~~~~~$小歪有一个整数 $s$ ，他想将 $s$ 分解成 $n$ 个非负整数，使得这 $n$ 个整数构成的数组 $\\{a_1,a_2,\dots,a_n\\}$ 满足： 

$~~~~~~~~~$$\bullet\ $$a_1+a_2+\dots+a_n$ 恰好为 $s$ ；  


$~~~~~~~~~$$\bullet\ $$\rm mex \\{a\\}$ 恰好为 $k$ 。 

  
$~~~~~~$非负整数数组的 $\operatorname{mex}$ 定义为没有出现在数组中的最小非负整数。例如 $\operatorname{mex} \\{1,2,3 \\} =0$ 、$\operatorname{mex} \\{0,2,2,5\\} =1$ 。

## 输入描述:
    
    
    $~~~~~~$每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\le T\le 10000\right)$ 代表数据组数，每组测试数据描述如下：  
      
    $~~~~~~$在一行上输入三个整数 $s,n,k \left(1\le s \le 10^9;\ 1\le n \le 10^6;\ 0 \le k \le 10^9 \right)$ ，含义与题干保持一致。  
      
    $~~~~~~$除此之外，保证所有的 $n$ 之和不超过 $10^6$ 。

## 输出描述:
    
    
    $~~~~~~$如果存在一种分解方案，在第一行上输出 $\rm YES$ ，随后，在第二行上输出 $n$ 个整数代表分解出的非负整数；否则，直接输出 $\rm NO$ 。  
      
    $~~~~~~$如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

示例1 

## 输入
    
    
    3
    6 3 3
    7 4 3
    6 6 0

## 输出
    
    
    NO
    YES
    4 0 1 2
    YES
    1 1 1 1 1 1


## 时空限制

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

Tags: 构造
Difficulty: 1400
# 小红的X型矩阵

## 题目描述

$~~~~~~$小红有一个大小为 $n \times n$ 的 $\texttt{0-1}$ 矩阵。小红可以对矩阵操作多次，每次可以任选其中其中一种操作：  
$~~~~~~~~~$$\bullet\ $操作一：选择矩阵的一个元素进行反转，即使得 $0$ 变为 $1$ ，$1$ 变为 $0$ ；  


$~~~~~~~~~$$\bullet\ $操作二：将矩阵循环右移或循环下移一格。例如，![\\left\(\\begin{matrix}<br />1 & 0 & 1 \\\\<br />0 & 1 & 0 \\\\<br />1 & 0 & 0 \\\\<br />\\end{matrix}\\right\) \\ce{->\[\\text{右移}\]} \\left\(\\begin{matrix}<br />1 & 1 & 0 \\\\<br />0 & 0 & 1 \\\\<br />0 & 1 & 0 \\\\<br />\\end{matrix}\\right\) \\ce{->\[\\text{下移}\]} \\left\(\\begin{matrix}<br />0 & 1 & 0 \\\\<br />1 & 1 & 0 \\\\<br />0 & 0 & 1 \\\\<br />\\end{matrix}\\right\)](https://www.nowcoder.com/equation?tex=%5Cleft\(%5Cbegin%7Bmatrix%7D%0A1%20%26%200%20%26%201%20%5C%5C%0A0%20%26%201%20%26%200%20%5C%5C%0A1%20%26%200%20%26%200%20%5C%5C%0A%5Cend%7Bmatrix%7D%5Cright\)%20%5Cce%7B-%3E%5B%5Ctext%7B%E5%8F%B3%E7%A7%BB%7D%5D%7D%20%5Cleft\(%5Cbegin%7Bmatrix%7D%0A1%20%26%201%20%26%200%20%5C%5C%0A0%20%26%200%20%26%201%20%5C%5C%0A0%20%26%201%20%26%200%20%5C%5C%0A%5Cend%7Bmatrix%7D%5Cright\)%20%5Cce%7B-%3E%5B%5Ctext%7B%E4%B8%8B%E7%A7%BB%7D%5D%7D%20%5Cleft\(%5Cbegin%7Bmatrix%7D%0A0%20%26%201%20%26%200%20%5C%5C%0A1%20%26%201%20%26%200%20%5C%5C%0A0%20%26%200%20%26%201%20%5C%5C%0A%5Cend%7Bmatrix%7D%5Cright\))。 

$\,\,\,\,\,\,\,\,\,\,$小红想知道，最少需要多少次**操作一** ，可以让矩阵变成一个 _X 型矩阵_ 。请你帮助小红解决这个问题。  


  


$\,\,\,\,\,\,\,\,\,\,$一个矩阵被称为  _X 型矩阵_ ，当且仅当两条对角线上的数字全为 $1$ ，而其他位置都是 $0$（$a_{ii} = 1, a_{i, n - i + 1} = 1$，其他都为 $0$ ），形如：

$\left(\begin{matrix} 1 & 0 & \dots & 0 & 1 \\\ 0 & 1 & \dots & 1 & 0 \\\ \vdots & \vdots & \ddots & \vdots & \vdots \\\ 0 & 1 & \dots & 1 & 0 \\\ 1 & 0 & \dots & 0 & 1\\\ \end{matrix}\right)$ 

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$第一行输入一个整数 $n \left(1 \leq n \leq 1000\right)$ 代表矩阵的大小。  
    $\,\,\,\,\,\,\,\,\,\,$此后 $n$ 行，第 $i$ 行输入 $n$ 个整数 $a_{i,1},a_{i,2},\dots,a_{i,n} \left(0\le a_{i,j} \le 1\right)$ 代表矩阵中的元素。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$在一行上输出一个整数，表示最少需要多少次操作一才能得到一个 X 型矩阵。

示例1 

## 输入
    
    
    3
    1 0 1
    0 1 0
    1 0 0

## 输出
    
    
    1

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,\,$选择 $(3, 3)$，进行一次操作一，即可得到 X 型矩阵。

示例2 

## 输入
    
    
    5
    1 0 0 1 0
    1 0 0 0 0
    0 0 0 1 1
    1 1 0 0 1
    1 0 1 1 0

## 输出
    
    
    8


## 时空限制

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

Tags: 枚举
Difficulty: 2000
# 小红的数组回文值

## 题目描述

$\,\,\,\,\,\,\,\,\,$小红定义一个数组的回文值是：修改最少数量的元素值得该数组回文，这个次数即数组的回文值。  
$\,\,\,\,\,\,\,\,\,$例如，$\\{3,2,4,3\\}$ 的回文值是 $1$ ，只需要将第二个元素修改为 $4$ 即可。  


$\,\,\,\,\,\,\,\,\,$现在小红拿到了一个数组，她希望你求出所有 _子序列_ 的回文值之和。你能帮帮她吗？ 

  


$\,\,\,\,\,\,\,\,\,$定义 _子序列_ 为从数组中从左到右取出若干个元素（可以不取、可以全取、可以不连续）形成的数组。

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,$第一行输入一个整数 $n \left( 1\leq n \leq 2000\right)$ 代表数组中的元素数量。  
    $\,\,\,\,\,\,\,\,\,$第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n\left( 1\leq a_i \leq 10^9\right)$ 代表数组元素。  
    

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,$在一行上输出一个整数，代表所有子序列的回文值之和。由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。

示例1 

## 输入
    
    
    3
    1 2 3

## 输出
    
    
    4

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,$$\{1,2\}$ 、$\{1,3\}$ 、$\{2,3\}$ 和 $\{1,2,3\}$ 的回文值都是 $1$ 。其余子序列的回文值均为 $0$ 。

示例2 

## 输入
    
    
    4
    999 999 999 999

## 输出
    
    
    0


## 时空限制

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

Tags: 组合数学
Difficulty: 1900
# 会赢吗？

## 题目描述

$\,\,\,\,\,\,\,\,\,$小歪正在玩《$\sf ***:**$》。他知道下一个头目伤害最高的那一段招式可以造成 $w$ 点伤害，而自己现在只有 $h$ 点生命。当生命小于等于 $0$ 时，就寄了。  


$\,\,\,\,\,\,\,\,\,$他想整个花活，无伤过关，但吃下伤害最高的那一段招式一次。 

$\,\,\,\,\,\,\,\,\,$会赢吗？

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,$第一行上输入一个小数点后位数不超过 $6$ 位的实数 $w$ 和一个整数 $h \left(1\le h,w \le 500 \right)$ 代表斩杀技伤害、目前生命上限。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,$会赢的话，在一行上输出 $\rm YES$ ；否则，直接输出 $\rm NO$ 。

示例1 

## 输入
    
    
    499.123456 499

## 输出
    
    
    NO

## 说明
    
    
    $~~~~~~$吃下这一招后生命降为 $-0.123456$ ，寄了。

示例2 

## 输入
    
    
    1.999999 2

## 输出
    
    
    YES

## 说明
    
    
    $~~~~~~$吃下这一招后生命降为 $0.000001$ ，还活着，会赢的。

示例3 

## 输入
    
    
    1 1

## 输出
    
    
    NO


## 时空限制

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

Tags: 模拟
Difficulty: 400
# 能做到的吧

## 题目描述

$\,\,\,\,\,\,\,\,\,$小苯有一个正整数 $x$，他希望用最多一次交换数位操作（即选择 $x$ 中的两个数位交换位置）把 $x$ 变大，请问他能否做到呢。  


## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,$每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\le T\le 100\right)$ 代表数据组数，每组测试数据描述如下：  
    
    
      
    
    
    $\,\,\,\,\,\,\,\,\,$在一行上输入一个整数 $x\ (0 \leq x \leq 10^{20})$ ，表示小苯询问的数字 $x$ 。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,$对于每一组测试数据，如果小苯能做到，在一行上输出 $\rm YES$ ；否则，直接输出 $\rm NO$ 。

示例1 

## 输入
    
    
    2
    112
    321

## 输出
    
    
    YES
    NO

## 说明
    
    
    对于第一组测试数据，可以交换第一个数位 $1$ 和第三个数位 $2$，数字变成 $211$ 比原来更大，因此输出 YES。


## 时空限制

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

Tags: 模拟
Difficulty: 400
# 会赢的！

## 题目描述

$\,\,\,\,\,\,\,\,\,$在一个无限大的二维网格内，阿龙和小歪正在玩一场游戏。我们使用 $(i,j)$ 表示网格中从上往下数第 $i$ 行和从左往右数第 $j$ 列的单元格。规则如下：  


$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\bullet\,$两人共同操作一个棋子，开始位置为 $(0,0)$ ； 

$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\bullet\,$每个回合每人可以将棋子向下或向右移动一格，向下移动一格即抵达 $(x+1,y)$ 、向右移动一格即抵达 $(x,y+1)$ ； 

$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\bullet\,$对于给定的终点 $(x,y)$ ，在谁的回合中有机会将棋子走到，谁就能胜利；如果谁都不能到达，则视为平局； 

$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\bullet\,$阿龙先手，双方均采取最优决策（尽可能让自己赢，自己赢不了则尽可能平局）； 

$\,\,\,\,\,\,\,\,\,$谁能赢呢。 

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,$每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\le T\le 10^4\right)$ 代表数据组数，每组测试数据描述如下：
    
      
    
    
    $\,\,\,\,\,\,\,\,\,$在一行上输入两个整数 $x,y \left( -100\leq x,y\leq 100\right)$ 代表终点。保证与起点不重合。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,$如果最后阿龙获胜，在一行上输出 $\rm YES$ ；如果小歪获胜，输出 $\rm NO$ ；否则为平局，直接输出 $\rm PING$ 。

示例1 

## 输入
    
    
    3
    1 1
    1 0
    -1 -1

## 输出
    
    
    NO
    YES
    PING


## 时空限制

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