yl-9/probench huggingface dataset:
# 材料打印

## 题目描述

小Y今天去打印毕业材料。这些材料中有 $\mathrm{a}$ 页既可以黑白打印也可以彩印，还有 $\mathrm{b}$ 页必须彩印。黑白打印一页需要 $\mathrm{x}$ 元，彩色打印一页需要 $\mathrm{y}$ 元，请计算他最少需要多少钱？  


  


## 输入描述:
    
    
    第一行给出一个整数 $\mathrm{T}(\mathrm{1 \le T \le 10^5})$ ，表示数据组数。
    
      
    
    
    对于每组测试数据，给出一行共四个整数 $\mathrm{a,b,x,y}(\mathrm{1 \le a,b,x,y \le 10^9})$。  
    

## 输出描述:
    
    
    每组测试数据输出一行，一个整数，表示小Y的最小花费。

示例1 

## 输入
    
    
    3
    2 2 3 4
    2 2 4 3
    1 14514 1 919810

## 输出
    
    
    14
    12
    13350122341


## 时空限制

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

Tags: 数学
Difficulty: 600
# %%%

## 题目描述

对于一个整数 $\mathrm{n}$，存在一种操作：将 $\mathrm{n}$ 对一个不大于 $\mathrm{n}$ 的正整数 $\mathrm{mod}$ 取余（$\mathrm{1\leq mod\leq n}$），并将结果再赋值给 $\mathrm{n}$。（即：$\mathrm{n = n \% mod}$）  


  


请问 $\mathrm{n}$ 变为 $\mathrm{0}$ **最多** 需要多少次操作？ 

## 输入描述:
    
    
    第一行给定一个整数 $\mathrm{T}(\mathrm{1 \le T \le 10^5})$，下面为 $\mathrm{T}$ 组数据，每行给定一个整数 $\mathrm{n}(\mathrm{0 \le n \le 10^{18}})$。
    
      
    

## 输出描述:
    
    
    输出 $\mathrm{T}$ 行，每行一个整数。

示例1 

## 输入
    
    
    3
    0
    3
    114514

## 输出
    
    
    0
    2
    16


## 时空限制

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

Tags: 贪心
Difficulty: 700
# 迷宫

## 题目描述

给定一个 $\mathrm{n \times m}$ 的迷宫，迷宫由 "#" 与"." 两种字符组成。其中 "#" 代表障碍物，"." 表示空地。迷宫中还有一个起点 "S" 和一个终点 "E" ，它们都可以视为空地。 

  


由于近期迷宫发生了塌方，导致起点和终点之间可能并不连通。幸运的是，你拥有一种超能力——在迷宫中移动时（移动方向为上、下、左、右四个方向之一），可以在当前位置朝任一方向（上、下、左、右四个方向之一）释放激光。激光能够清除该方向上所有的障碍物，并且这种超能力**至多** 只能使用一次。 

  


现在，你需要判断是否能利用这种超能力成功从起点到达终点。

## 输入描述:
    
    
    第一行给定两个整数 $\mathrm{n,m}(\mathrm{2 \le n,m \le 1000})$ ，分别表示迷宫的行数和列数。
    
      
    
    
    下面 $\mathrm{n}$ 行，每行 $\mathrm{m}$ 个字符，描述迷宫的具体布局。字符只包含 "#"、"."、"S" 和 "E"，并且起点与终点有且仅有一个。

## 输出描述:
    
    
    能够到达终点输出 $\mathrm{YES}$ ；否则输出 $\mathrm{NO}$。

示例1 

## 输入
    
    
    4 5
    .####
    S####
    .####
    .E###

## 输出
    
    
    YES

示例2 

## 输入
    
    
    4 5
    ..###
    S####
    #####
    ##.E#

## 输出
    
    
    YES

## 说明
    
    
    显然可以从起点出发，到达$\mathrm{(1,2)}$处并向下方使用超能力，此时可以从起点到达终点。

示例3 

## 输入
    
    
    4 5
    ..###
    S####
    #####
    ###E#

## 输出
    
    
    NO


## 时空限制

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

Tags: 广度优先搜索(BFS), 搜索
Difficulty: 1300
# 又是一年毕业季

## 题目描述

又是一年一度的毕业季，一群学生准备去拍摄毕业照。 

  


具体来说，一共有 $\mathrm{n}$ 个同学共同参与拍照，第 $\mathrm{i}$ 个学生两次眨眼的时间间隔为 $\mathrm{a_i}$ 。在拍照开始前，我们可以认为所有人在第 $\mathrm{0}$ 秒都眨了一次眼。 

  


由于调整相机需要一定的时间，因此在最初的2秒内不能进行拍照（**即**需要保证** 拍照的时刻 **$\mathrm{x \ge 2}$）。请计算，为了确保每个人的眼睛都处于睁开状态，至少需要等待多少秒后才能进行拍照。 

## 输入描述:
    
    
    第一行给出一个整数 $\mathrm{T}(\mathrm{1 \le T \le 5 \times 10^4})$ ，表示数据组数。
    
      
    
    
    对于每组测试数据，第一行给出一个整数 $\mathrm{n}(\mathrm{1 \le n \le 2\times 10^5},\mathrm{\sum n \le 2\times 10^5})$，表示总人数。第二行给出 $\mathrm{n}$ 个整数 $\mathrm{a_i}(\mathrm{2 \le a_i \le 10^9})$，依次表示每个人两次眨眼的间隔时间。

## 输出描述:
    
    
    每组测试数据输出一个整数，表示最小等待时间。

示例1 

## 输入
    
    
    3
    4
    2 4 6 5
    5
    6 2 5 3 2333333
    8
    11 4 5 14 19 19 8 10

## 输出
    
    
    3
    7
    2


## 时空限制

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

Tags: 筛法, 数论
Difficulty: 1400
# 多米诺骨牌

## 题目描述

小利同学摆放了 $\mathrm{n}$ 张多米诺骨牌，第 $\mathrm{i}$ 张骨牌高为 $\mathrm{h_i}$，摆放在位置 $\mathrm{x_i}$。该骨牌向后倒塌时会使位于 $\mathrm{[x_i,h_i+x_i]}$ 区间(包含 $\mathrm{x_i,h_i+x_i}$)的骨牌全部倒塌。  
  
小利同学摆放完骨牌就开心的出去玩耍了。结果小金同学发现了这些骨牌，他想趁小利不在，选择**不超过** $\mathrm{m}$ 张骨牌并依次向后推倒，请算算**最多** 会有多少张骨牌倒塌。  
  
保证任意位置上至多存在一张骨牌。

## 输入描述:
    
    
    第一行给出一个整数 $\mathrm{T}(\mathrm{1 \le T \le 5\times 10^4})$ ，表示数据组数。  
      
    每组数据第一行给出两个整数 $\mathrm{n,m}(\mathrm{1 \le m \le n \le 2\times 10^5},\mathrm{\sum n \le 2\times 10^5})$，分别表示骨牌总数与最多可推倒骨牌数。  
      
    第二行依次给出 $\mathrm{n}$ 个整数，表示骨牌高度 $\mathrm{h_i}(\mathrm{1 \le h_i \le 10^9})$ 。  
      
    第三行依次给出 $\mathrm{n}$ 个不同整数，表示骨牌位置 $\mathrm{x_i}(\mathrm{1 \le x_i \le 10^9})$ 。

## 输出描述:
    
    
    每组测试数据输出一个整数，表示骨牌最多倒塌数。

示例1 

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

## 输出
    
    
    3
    6
    5


## 时空限制

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

Tags: 模拟, 思维
Difficulty: 1500
# 自爆机器人

## 题目描述

在一条水平线上存在着一个自爆机器人和一只怪物。自爆机器人初始坐标为 $\mathrm{0}$ ，怪物坐标为 $\mathrm{n}$ 。自爆机器人在启动后将向怪物以 $\mathrm{1}$ 坐标每秒的速度移动，并在遇到怪物的瞬间爆炸，造成大小等同于行动时间的伤害。  
  
你是这款游戏的玩家，在机器人移动过程中你可以在给定的 $\mathrm{m}$ 个**不同整数坐标** 上任意建造或摧毁墙壁（**同一坐标可以重复建造、摧毁墙壁** ）。如果机器人在移动过程中撞到墙壁，其会向反方向移动。  
  
当然，为了防止玩家无限制的增加爆炸伤害，游戏开发者还给自爆机器人设置了最大起爆时间 $\mathrm{t}$ 。一旦耗时达到 $\mathrm{t}$ 机器人会立刻自爆。机器人只有在与怪物位于同一坐标时引爆才会对其造成伤害，现在请你最大化自爆机器人对怪物造成的伤害。

## 输入描述:
    
    
    第一行给出一个整数 $\mathrm{T}(\mathrm{1 \le T \le 10^4})$ ，表示数据组数。  
      
    对于每组测试数据：
    
      
    
    
    第一行给出三个整数 $\mathrm{n,m}(\mathrm{1 \le m < n \le 2\times10^5})$,$\mathrm{t}(\mathrm{1 \le t \le 2 \times 10^5})$，表示坐标数，可建造或摧毁墙壁的坐标数，以及最大起爆时间。
    
      
    
    
    第二行给出 $\mathrm{m}$ 个不同整数，表示可建造、摧毁墙壁的坐标 $\mathrm{x_i}(\mathrm{1 \le x_i < n})$。
    
      
    
    
    保证所有测试数据中  $\mathrm{\sum n \le 2\times10^5,\sum t \le 2\times10^5}$

## 输出描述:
    
    
    每组测试数据输出一个整数，为可能对怪物造成的最大伤害。

示例1 

## 输入
    
    
    1
    4 2 8
    2 3

## 输出
    
    
    8

## 说明
    
    
    显然可以在机器人坐标位于 $\mathrm{(2,3)}$ 时，将坐标 $\mathrm{2}$ 与坐标 $\mathrm{3}$ 建上墙壁，等待机器人墙壁之间走两个来回后破坏墙壁。机器人遇到怪物自爆时消耗的总时间为 $\mathrm{3+1+1+1+2=8}$。

示例2 

## 输入
    
    
    1
    15 4 28
    4 6 10 13

## 输出
    
    
    27

## 说明
    
    
    一种可行的方案是，当机器人行进过程中，坐标位于 $\mathrm{(4,10)}$ 之间时，将坐标 $\mathrm{4}$ 与坐标 $\mathrm{10}$ 建上墙壁，等待机器人在墙壁间走一个来回后破坏墙壁，让机器人走向怪物爆炸。此时机器人消耗的总时间为 $\mathrm{10+6+11=27}$。

示例3 

## 输入
    
    
    2
    4 1 3
    2
    23 4 43
    13 17 9 2

## 输出
    
    
    0
    39


## 时空限制

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

Tags: 背包问题, 动态规划
Difficulty: 2000
# 大鱼吃小鱼

## 题目描述

现在小w正在玩一款经典游戏——大鱼吃小鱼。  
  
游戏规则如下：玩家操控一条初始重量为 $\mathrm{x}$ 的鱼，它的目标是吃掉所有**不超过** 自身当前重量的鱼。每当吃掉一条重量为 $\mathrm{y}$ 的鱼，那么自身重量也会立即增长 $\mathrm{y}$。  
  
在游戏过程中，共会陆续出现 $\mathrm{n}$ 条鱼。其中第 $\mathrm{i}$ 条鱼重 $\mathrm{y_i}$，其出现时间段为 $\mathrm{\left[l_i,r_i\right)}$，即这条鱼会在时刻 $\mathrm{l_i}$ 出现，并在时刻 $\mathrm{r_i}$ 前消失（**包含** $\mathrm{l_i}$**但不包含** $\mathrm{r_i}$）。只有当前时刻位于 $\mathrm{\left[l_i,r_i\right)}$ 时，小w才能操作自己的鱼去吃掉它。  
  
鉴于小w的手速非凡，吃鱼的耗时可以忽略不计。不过最近他懒癌犯了，因此他打算只选择某一时刻进行捕食，并最大化他的鱼的重量。请计算他的鱼可能达到的最大重量。

## 输入描述:
    
    
    第一行给出一个整数 $\mathrm{T}(\mathrm{1 \le T \le 5\times 10^4})$ ，表示数据组数。  
      
    对于每组测试数据：  
      
    第一行给出两个整数 $\mathrm{n,x}(\mathrm{1 \le n \le 10^5},\mathrm{\sum n \le 10^5},\mathrm{1 \le x \le 10^9})$ ，表示鱼的总数与小w鱼的初始重量。  
      
    后面 $\mathrm{n}$ 行，每行为三个整数 $\mathrm{l_i,r_i,y_i}(\mathrm{1 \le l_i < r_i \le 10^9},\mathrm{1 \le y_i \le 10^9})$ 。

## 输出描述:
    
    
    一个整数，为小w的鱼可能达到的最大重量。

示例1 

## 输入
    
    
    2
    2 17
    3 4 9
    9 11 8
    4 1
    1 2 2
    2 4 1
    3 5 2
    4 5 3

## 输出
    
    
    26
    4

## 说明
    
    
    第一组样例中，小w鱼的初始重量为17，第一条鱼出现时间段为 $\mathrm{[3,4)}$，重量 $\mathrm{9}$ ；第二条鱼出现时间段为 $\mathrm{[9,11)}$，重量 $\mathrm{8}$ 。显然选择 $\mathrm{[3,4)}$ 内的任意时刻进行捕食最优。
    
      
    
    
    第二组样例中，小w鱼的初始重量为1，四条鱼的出现时间段与重量依次为：时间段 $\mathrm{[1,2)}$，重量 $\mathrm{2}$ ；时间段 $\mathrm{[2,4)}$，重量 $\mathrm{1}$ ；时间段 $\mathrm{[3,5)}$，重量 $\mathrm{2}$ ；时间段 $\mathrm{[4,5)}$，重量 $\mathrm{3}$ 。显然选择 $\mathrm{[3,4)}$ 内的任意时刻进行捕食最优。

示例2 

## 输入
    
    
    1
    10 20
    13 14 41
    10 29 3
    3 12 25
    10 22 69
    12 22 11
    14 24 34
    18 35 6
    5 15 59
    8 9 21
    18 22 41

## 输出
    
    
    196


## 时空限制

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

Tags: 数据结构, 线段树, 树状数组, 思维, 暴力
Difficulty: 2200
# 骰子魔术

## 题目描述

jackle 正在给他的朋友表演一个关于骰子的魔术：  


  * jackle 会拿出一枚骰子，骰子的表面分别写上了从 $1\backsim 500$ 的数字，朋友会随便说一个 $1\backsim 500$ 之间的点数，jackle 都能保证百分之百的掷出这个点数。 

当然 jackle 有备而来，他准备了 $n$ 枚特殊的骰子，第 $i$ 枚特殊骰子，可以保证每次掷出的点数都为 $a_i$。  
jackle 想问你，他能不能只拿出一枚事先准备好的特殊骰子，成功完成这次魔术。

## 输入描述:
    
    
    第一行输入 $2$ 个正整数 $n\ (1\leq n\leq 1000)$，$x\ (1\leq x\leq 500)$，分别表示 jackle 准备的特殊骰子数量，朋友说的那个点数。  
    第二行输入 $n$ 个正整数 $a_i\ (1\leq a_i\leq 500)$，分别表示每枚特殊骰子可以掷出的点数。

## 输出描述:
    
    
    如果 jackle 可以成功完成这次魔术，请你输出 YES；否则请你输出 NO。

示例1 

## 输入
    
    
    5 3
    1 2 1 3 12

## 输出
    
    
    YES

## 说明
    
    
    jackle 可以选择第 $4$ 个骰子，因为 $a_4 = x = 3$，所以他能百分之百掷出这个朋友说出的点数，所以可以完成这次魔术。


## 时空限制

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

Tags: 思维
Difficulty: 600
# 最少剩几个？

## 题目描述

给定一个长度为 $n$ 的序列 $a$，如果当前序列长度至少为 $2$，那么你每次可以做如下两种操作之一： 

  1. 选择 $i,j\ (i\not =j)$，如果满足 $a_i+a_j$ 是奇数，那么你可以同时删除 $a_i,a_j$。 
  2. 选择 $i,j\ (i\not =j)$，如果满足 $a_i\times a_j$ 是奇数，那么你可以同时删除 $a_i,a_j$。 



你可以执行上面的操作无数次，只要你满足操作条件，jackle 想问你序列最少剩几个数？

## 输入描述:
    
    
    第一行输入 $1$ 个正整数 $n\ (1\leq n\leq 10^5)$，表示序列的长度。  
    第二行输入 $n$ 个正整数 $a_i\ (1\leq a_i\leq 10^9)$。

## 输出描述:
    
    
    输出序列最少剩几个数？

示例1 

## 输入
    
    
    1
    114514

## 输出
    
    
    1

## 说明
    
    
    只有一个数，啥也操作不了。

示例2 

## 输入
    
    
    2
    9 9

## 输出
    
    
    0


## 时空限制

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

Tags: 贪心
Difficulty: 600
# 两个函数

## 题目描述

jackle 给定两个函数：  


  * $f(x)=ax$ 
  * $g(x)=\begin{cases} f(x)&x=1\\\\\sum_{i=1}^{x-1}f(f(i)) &x>1\end{cases}$ 

他有 $Q$ 次询问，每次给定 $a,x$，请你计算 $g(x)\mod 998244353$ 的结果。

## 输入描述:
    
    
    第一行输入 $1$ 个正整数 $Q\ (1\leq Q\leq 10^5)$，表示询问次数。  
    接下来 $Q$ 行，每行输入 $2$ 个正整数 $a,x\ (1\leq a,x\leq 10^9)$。

## 输出描述:
    
    
    对于每组询问，输出 $g(x)\mod 998244353$ 的结果。

示例1 

## 输入
    
    
    3
    1 1
    2 2
    9982 44353

## 输出
    
    
    1
    4
    572321601


## 时空限制

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

Tags: 数学
Difficulty: 900
# 切割 01 串 2.0

## 题目描述

jackle 在校赛的时候出过一道 "切割 01 串" 的题目，如今他又出了一道切割 01 串的题目：  
给定一个长度为 $n$ 的 $01$ 串，定义如下操作为一次 "切割"：  


  * 将**长度大于 $1$ **的字符串分割为两个**非空的连续字串** ，记分割出来的左侧字串 $a$ 中 $0$ 的出现次数为 $C_0$，右侧字串 $b$ 中 $1$ 出现的次数为 $C_1$，需要满足 $L\leq |C_0-C_1|\leq R$。 

你每次切割完，都会得到两个新 $01$ 串，你可以继续选择这些已经被你切出来的 $01$ 串做切割，只要满足切割条件。 

jackle 想问你最多可以切割多少次？ 

## 输入描述:
    
    
    第一行输入 $3$ 个整数，$n\ (1\leq n \leq 500)$，$L,R\ (0\leq L \leq R \leq 500)$，分别表示字符串长度，和题目中的两个参数。  
    第二行输入 $1$ 个长度为 $n$ 的 $01$ 串。

## 输出描述:
    
    
    输出最多能切割多少次？

示例1 

## 输入
    
    
    6 2 3
    011011

## 输出
    
    
    3

## 说明
    
    
    其中一种切割次数最多的切法如下：  
    第一次切割可以切：$0\ |\ 11011$，然后选择 $11011$ 这个串继续做切割。  
    第二次切割可以切：$1\ |\ 1011$，然后选择 $1011$ 这个串继续做切割。  
    第三次切割可以切：$1\ |\ 011$。


## 时空限制

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

Tags: 动态规划, 区间dp
Difficulty: 1500
# and xor or

## 题目描述

给定一个长度为 $n$ 的序列 $a$，jackle 想让你求出有多少个区间 $[l,r]$ 满足如下条件：  


  * $1\leq l\leq r\leq n$ 
  * $2^{k_1}\leq (a_l\ \&\ a_{l+1}\ \&...\&\ a_r)\oplus(a_l\ |\ a_{l+1}\ |...|\ a_r)< 2^{k_2}$ 

其中 $\&$，$|$，$\oplus$，分别表示按位与，按位或，按位异或。

## 输入描述:
    
    
    第一行输入 $3$ 个整数 $n\ (1\leq n\leq 5\times 10^5)$，$k_1, k_2\ (0\leq k_1<k_2\leq 10^9)$。  
    第二行输入 $n$ 个整数 $a_i\ (0\leq a_i\leq 10^{18})$。

## 输出描述:
    
    
    输出满足条件的区间数量。

示例1 

## 输入
    
    
    4 0 2
    2 1 4 3

## 输出
    
    
    1

## 说明
    
    
    只有区间 $[1,2]$ 满足条件：$2^0\leq (2\ \& \ 1)\oplus(2\ |\ 1)=3<2^2$

示例2 

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

## 输出
    
    
    14


## 时空限制

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

Tags: 数据结构, ST表, 二分, 分治, 枚举, 位运算
Difficulty: 1900
# 绝妙的手法

## 题目描述

本题出题时想到的贪心做法是错误的，评测数据也是按照出题时的std造的，目前本题没有正确解法，不建议大家做这道题。

  


给定一个长度为 $n$ 的序列 $A$，你每次可以做如下操作： 

  * 每次选择**两个****不同** 的下标 $i,j$，令 $A_i= A_i+A_j$ 

jackle 想问你最少操作几次，可以使得序列中**恰好有** $m$**个****正数** 。

## 输入描述:
    
    
    注意本题有多组测试数据。
    
    第一行先输入 $1$ 个整数 $T(1\leq T\leq 2\times 10^5)$，表示数据组数。
    
    对于每组测试数据：
    
    第一行输入 $2$ 个整数 $n,m\ (1\leq n \leq 2\times 10^5,0\leq m\leq 2\times 10^5)$。
    
    第二行输入 $n$ 个整数 $A_i\ (-10^{12}\leq A_i \leq 10^{12})$。
    
    题目保证 $\sum n\leq 2\times 10^5$。

## 输出描述:
    
    
    对于每组测试数据：
    
    如果能通过操作，使得序列中恰好有 $m$ 个正数，请你输出最小操作次数；否则请你输出 $-1$。

示例1 

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

## 输出
    
    
    1

## 说明
    
    
    显然操作一次即可：选择 $i=1,j=4$，令 $A_1= A_1+A_4=-1+2=1$，操作完之后 $A_1=1$，那么此时序列中恰好 $3$ 个正数。

示例2 

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

## 输出
    
    
    -1

## 说明
    
    
    由于所有数都是 $0$，所以无论怎么执行 $A_i=A_i+A_j$，序列中的数都还是 $0$，所以一定无法操作使得序列恰好出现 $3$ 个正数。

示例3 

## 输入
    
    
    2
    4 2
    -10 1 1 1
    6 4
    4 -2 -2 -3 2 -4

## 输出
    
    
    1
    2


## 时空限制

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

## 题目描述

在坐标轴 $1$ 到 $n$ 的 $n$ 个位置上 

有长度为 $a_i$ 的 $n$ 根木棒 

其下会围成一个不规则多边形（详见样例） 

你可以多次交换不同相邻的木棒，求其下最大覆盖面积 $S$ 

## 输入描述:
    
    
    第一行输入 $n$ 
    
    接下来输入一行包括 $n$ 个正整数 $a_i$
    
    $1\le n \le 2× 10^6; 1\le a_i \le 2× 10^6$

## 输出描述:
    
    
    请输出 $n$ 根木棒的最大围成面积 $S$
    
    为了输出方便，请**四舍五入** 后保留两位小数

示例1 

## 输入
    
    
    3
    3 1 2

## 输出
    
    
    4.50

## 说明
    
    
    ![](https://uploadfiles.nowcoder.com/images/20240910/0_1725968801590/11EABDFD1149A633608C3DB73880577F)
    
      
    
    
    交换第1、2根木棒，变成 [1, 3, 2]
    
    面积从： (3+1)*1/2+(1+2)*1/2=3.5
    
    变为：(1+3)*1/2+(3+2)/2=4.5
    
    不存在更大的面积

示例2 

## 输入
    
    
    2
    5 5

## 输出
    
    
    5.00

示例3 

## 输入
    
    
    1
    3

## 输出
    
    
    0.00


## 时空限制

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

## 题目描述

在斗地主中连续的一组数组叫顺子，如$[3,4,5,6,7], [9,8,7,6,5]$; 

在这里为了方便将 $1, 2$ 也记入顺子中，且顺子长度没有任何限制，如 $[1,2,3], [5]$ 均是顺子 

可这样求最长顺子长度太无趣了... 

于是聪明的你引入了鬼牌的概念、鬼可以变为 $1$ 到 $m$ 中任何你想要的牌 

好了，现在求可以组成的最长顺子长度 

  


\--赛后补充： 

题目中最长顺子中的牌可以是原本中任意一张牌or鬼牌，组成的顺子必须连续无中断（排序后为公差为1的等差数列） 

## 输入描述:
    
    
    第一行输入 $n,m,k$，分别表示有 $n$ 张牌介于 $1$ 到 $m$ 之间，另外有 $k$ 张鬼牌 (共$n+k$张牌)
    
    第二行输入 $n$ 个正整数 $a_i$，表示 $n$ 张牌的点数
    
    $1\le n \le 5× 10^5; 1\le m\le 2×10^9; 0\le k\le 2×10^9;1\le a_i \le m$  
    

## 输出描述:
    
    
    输出一个非负整数表示可行顺子的最大长度

示例1 

## 输入
    
    
    3 3 0
    1 2 3

## 输出
    
    
    3

示例2 

## 输入
    
    
    3 5 1
    1 3 5

## 输出
    
    
    3

## 说明
    
    
    鬼牌变 4，组成 [3, 4, 5]的三顺子

示例3 

## 输入
    
    
    1 3 5
    1

## 输出
    
    
    3

## 说明
    
    
    鬼牌只能变1或2或3，故最大长度为3

示例4 

## 输入
    
    
    5 13 0
    10 11 12 13 1

## 输出
    
    
    4

## 备注:
    
    
    本题输入量较大，请使用较快的读入方式
    
    本题的顺子可能与你认识的顺子不一样，请仔细阅读本题中顺子定义。


## 时空限制

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

## 题目描述

圆上有$n$等分点 

你即将给其中$k$个点染上红色。 

如果染色后，存在两个红点，其连线能平分圆的面积，则认为这种染色方式是美丽的； 

请问，对$k$个点染色有多少种不同染色方式能画出一个美丽的图？

其中对$n$个点标记为$1,2,3...n$；如果两个圆$A$ $B$染色不同，当且仅当存在1个点在$A$中被染为红色，而图$B$中没有染色

请将最终结果对 $10^9+7$ $(1000000007 )$ 取模 

## 输入描述:
    
    
    第一行输入一个正整数$T$，表示$T$组数据
    
    接下来$T$行，每行两个正整数$n$,$k$
    
    $1\le T\le10^6; 0\le k \le n\le10^7 ; 2\le n$  
    

## 输出描述:
    
    
    每行输出一个数表示答案对 $10^9+7$ 取模的结果

示例1 

## 输入
    
    
    3
    2 0
    2 1
    2 2

## 输出
    
    
    0
    0
    1

示例2 

## 输入
    
    
    2
    4 2
    4 4

## 输出
    
    
    2
    1

## 备注:
    
    
    圆上n等分点的定义是：在圆的周长上均匀地选择n个点，使得相邻两个点之间的弧长相等。


## 时空限制

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 768 M，其他语言1536 M
64bit IO Format: %lld
# 暖鸭

## 题目描述

还记得什么是阶乘吗，现在不考这个... 

问给定  $T$ 组数据，每组数据给定 $l,r$ 

在所有的$l\le a \le b \le r$ 中，等可能地随机取一对$(a, b)$ 

求区间 $[a, b]$ 至少包含一个平方数的概率 

为了计算方便，最终答案乘上 $(r-l+1)*(r-l+2)$ 后对 $1000000007$取模 

## 输入描述:
    
    
    第一行输入一个 $T$，表示  $T$ 组数据
    
    接下来每行一组 $l,r$ 如题所示
    
    $1\le T \le 3 × 10^5; 1 \le  l \le r \le 1 × 10^{16}$  
    

## 输出描述:
    
    
    输出一个非负整数表示最终答案

示例1 

## 输入
    
    
    3
    1 1
    1 2
    1 3

## 输出
    
    
    2
    4
    6

## 说明
    
    
    [1,2] 中 a,b 有 [1,1], [1, 2], [2, 2]三种等可能区间，仅仅 [2, 2]没有包含完全平方数1
    
    故答案为 2/3
    
    输出 (2/3 * 3 * 2)%(1e9+7) = 4

示例2 

## 输入
    
    
    1
    3 5

## 输出
    
    
    8

## 备注:
    
    
    $1000000007 = 1×10^9+7$ 是个质数
    
      
    
    
    **本题输入量较大，请使用较快的读入方式**


## 时空限制

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

## 题目描述

在$n*m$大小的二维矩阵中每个格子的初始高度为 $a_{ij}$ 

俗话说万丈高楼平地起... 

你决定使用魔法：对于每个格子 $a_{ij}$ 如果其四周(上下左右)均有格子，且四周格子高度均大于等于 $a_{ij}$ 时实际高度会 $+1$，即 $a_{ij} = a_{ij} + 1$ 

你将会夜以继日充不停息，从上到下，从左到右遍历整个矩阵对于每个格子均使用一次魔法 

但是，慢慢的，你好像发现时间足够长久后，貌似整个矩阵高度均不会发生变化 

求最终矩阵的形态；为了输出方便，**请输出全部 $a_{ij}$ 的和以及 $a_{ij}$ 的异或和**

## 输入描述:
    
    
    第一行输入 $n$，$m$ 两个整数表示 $n$行$m$列的矩阵
    
    接下来 $n$ 行，每行 $m$ 个 $a_{ij}$ 表示初始平地的高度
    
    $1\le n,m \le 2 × 10^3; 1\le  a_{ij} \le 1 × 10^9$  
    

## 输出描述:
    
    
    输出一行两个整数
    
    分别表示最终状态下 $a_{ij}$ 的和 以及 $a_{ij}$ 的异或和

示例1 

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

## 输出
    
    
    40 0

## 说明
    
    
    第一次遍历：
    
    遍历到第 2 行第 2 列的数字2
    
    有2<=min(4,3,2,2),故变为
    
    2 4 2 2  
    3 **3** 2 2  
    2 2 2 2  
    2 2 2 2  
    
    
    遍历到第 2 行第 3 列的数字2，变为
    
    2 4 2 2  
    3 3 **3** 2  
    2 2 2 2  
    2 2 2 2
    
    遍历到第 3 行第 2 列的数字2，变为
    
    2 4 2 2  
    3 3 3 2  
    2 **3** 2 2  
    2 2 2 2
    
    遍历到第 3 行第 3 列的数字2，变为
    
    2 4 2 2  
    3 3 3 2  
    2 3 **3** 2  
    2 2 2 2
    
      
    
    
    第二次遍历：
    
    遍历到第 2 行第 2 列的数字3
    
    有3<=min(4,3,3,3),故变为
    
    2 4 2 2  
    3 **4** 3 2  
    2 3 3 2  
    2 2 2 2
    
      
    
    
    此后不会有任何改变
    
    和为 2+4+2+2+3+4+3+2+2+3+3+2+2+2+2+2=40
    
    异或和为 2^4^2^2^3^4^3^2^2^3^3^2^2^2^2^2=0

示例2 

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

## 输出
    
    
    28 4

## 说明
    
    
    最终结果：
    
    3 3 3
    
    3 4 3
    
    3 3 3

示例3 

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

## 输出
    
    
    8 0

示例4 

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

## 输出
    
    
    78 6

## 备注:
    
    
    注：$a_{ij} \le 1 × 10^9$仅限制初始状态，中间结果可能不满足该条件


## 时空限制

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

## 题目描述

多组样例 $T$ 

每输入三个数 $a,b,c$ 表示木棒长度 

你可以对任意边多次花费 $1$ 的代价将某条边长度 $+1$ 或 $-1$ 

使得最终的 $a,b,c$ 可以组成直角三角形 

求最小代价 

## 输入描述:
    
    
    第一行输入 $T$ 表示 $T$ 组样例
    
    每组样例输入三个正整数 $a,b,c$
    
      
    
    
    $1\le T \le 20; 1\le  a,b,c \le 2 × 10^{5}$  
    

## 输出描述:
    
    
    每组样例一个整数表示答案
    
    如果无法构成直角三角形输出 $-1$

示例1 

## 输入
    
    
    1
    3 5 4

## 输出
    
    
    0

## 说明
    
    
    本身就可以构成直角三角形

示例2 

## 输入
    
    
    3
    6 8 9
    5 12 13
    1 1 1

## 输出
    
    
    1
    0
    9

## 备注:
    
    
    你不需要输出中间过程
    
    但请保证中间过程中木棒长度均为正整数!


## 时空限制

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

## 题目描述

小H今天在学校里学习了语文，语文老师给大家讲解了什么是木桶效应，一个木桶能装多少的水取决于最短的那块木板，所以要想装更多的水应该减少短板。但小H认为木桶能装的水的体积 $v$ 应该是底面积 $s$ 乘上最短木板长度 $h_{min}$，而底面积与木桶周长的平方成正比，木桶周长则与木板数量 $m$ 成正比。因此体积最终取决于 $m^2 \times h_{min}$。所以增加短的木板也可能增大装水体积。现在有 $n$ 块木板，请你选择适当的木板使得装水体积最大，并且输出选择的木板方案。  


## 输入描述:
    
    
    第一行输入一个整数 $n$，表示木板的数量。  
    接下来一行输入 $n$ 个正整数 $h_i$，表示每块木板的长度。  
    $1\leq n \leq 2\times 10^5$  
    $1\leq h_i \leq 10^6$  
    

## 输出描述:
    
    
    第一行输出一个正整数 $m$ 表示选择的木板数量。  
    第二行输出 $m$ 个正整数表示选择木板的编号。输出编号从小到大排序，如果存在多个方案输出其中一种即可。  
    

示例1 

## 输入
    
    
    5
    7 1 3 8 4

## 输出
    
    
    4
    1 3 4 5

## 说明


## 备注:



## 时空限制

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

## 题目描述

小H今天在学校里学习了数学，学会了正整数的加减法。他很快就能计算出用双手表示的数进行加减运算得到的结果，老师看小H太骄傲了，决定考考小H。老师给小H一个数 $x$，询问小H用双手有多少种方案凑出 $x$。注意两只手可以直接表示一个$[1,10]$范围的数，也能表示两个$[1,5]$范围的数。每个数都可以选择做加法或减法。数学老师笑着说，为了帮你解决问题，我找了另外 $y$ 个同学帮你(所有同学的手指健全)。  
**注意，任意一个同学左右手表示的数不同或者计算时需要的操作符不同视为不同的方案。**  
由于答案方案数可能很大，对答案进行取模，模数为 $10^9+7$。 

## 输入描述:
    
    
    第一行输入两个整数 $x,y$，表示需要凑的整数，与帮忙的同学数量。  
    $-10^3\leq x\leq 10^3$  
    $0\leq y\leq 99$

## 输出描述:
    
    
    输出一行整数，表示所有不同方案的数量。

示例1 

## 输入
    
    
    8 0

## 输出
    
    
    4

## 说明
    
    
    所有方案为$\lbrace 3+5\rbrace,\lbrace 4+4\rbrace,\lbrace 5+ 3\rbrace,\lbrace 8\rbrace$

示例2 

## 输入
    
    
    4 0

## 输出
    
    
    6

## 说明
    
    
    所有方案为$\lbrace 1+3\rbrace,\lbrace 2+2\rbrace,\lbrace 3+ 1\rbrace,\lbrace 5-1\rbrace,\lbrace -1+5\rbrace,\lbrace 4\rbrace$

示例3 

## 输入
    
    
    1 7

## 输出
    
    
    280070350

## 说明


## 备注:



## 时空限制

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

## 题目描述

小H今天在学校里学习了生物，小H得知许多不同的生物都是由共同的原始祖先进化而来的。在一棵根节点编号为1且具有 $n$ 种不同物种的演化树上。物种 $i$ 将遗传信息向下传递到物种 $j$ 会产生 $d_{i,j}$ 的变异，其中变异信息 $d_{i,j}$ 是一个长为 $L$ 的01串。两物种 $u,v$ 之间的变异程度 $D_{u,v}$ 为 $u$ 到 $v$ 简单路径上的所有变异信息的异或和。  
老师给了小H一个包含 $m$ 个不同物种的种群，每个物种编号为 $a_i$，种群之内的基因多样性定义为 $\bigoplus\limits_{i=1}^{m-2}\bigoplus\limits_{j=i+2}^{m} D_{a_i,a_j}$。老师希望小H计算出给定种群的基因多样性。  


## 输入描述:
    
    
    第一行输入三个整数 $n$，$m$，$L$，分别表示 $n$ 个物种，基因编码长度为 $L$ 。  
    接下来 $n-1$ 行，每行输入两个整数 $u$，$v$，表示 $u$ 是 $v$ 的直接祖先。然后输入一个 01 串 $d_{u,v}$，表示 $u$ 和 $v$ 之间的变异信息。  
    接下来一行输入 $m$ 个整数 $a_i$，表示 $m$ 个物种的编号。  
    $3\leq m\leq n\leq 10^5$  
    $1\leq L \leq 100$  
    

## 输出描述:
    
    
    请输出长度为 $L$ 的种群基因多样性。

示例1 

## 输入
    
    
    3 3 4
    1 2 0101
    1 3 1101
    1 2 3

## 输出
    
    
    1101

## 说明


## 备注:



## 时空限制

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

## 题目描述

小H今天在学校里学习了物理，物理老师给了小H一把能量枪，这把枪能发射波长为 $\lambda$ 的能量波，小H在一个长度为 $L$ 的设备上进行发射，一束能量值为 $e$ 能量波 在 $x$ 位置发射，在 $x$ 处释放一次能量，该处能量值增加 $e$，能量波衰减能量绝对值减少一。当能量不为 0 时继续向右传递 $\lambda$ 距离进行一次能量释放衰减过程，直到能量衰减为 0。  
物理老师对小H发出了两种任务，任务一即发射能量波；任务二计算出设备上给定区间 $[l,r]$ 内的能量总和，请你帮他完成。 

## 输入描述:
    
    
    第一行输入两个整数 $K,L,\lambda$，分别表示任务总数和设备总长度以及波长。  
    接下来 $K$ 行，每行首先输入一个 $op$ 表示任务类型，  
    $op=0$，继续输入 $x_i,e_i$，表示能量波发射位置，能量波能量；  
    $op=1$，继续输入 $l_i, r_i$，表示每次查询的区间。  
    $1\leq K\leq 10^5$  
    $1\leq L\leq 10^5$  
    $1\leq \lambda \leq 10$  
    $1\leq x,l,r\leq L$  
    $1\leq |e|\leq L$

## 输出描述:
    
    
    对于每次查询，请输出对应区间内的能量总和。

示例1 

## 输入
    
    
    5 10 3
    0 1 4
    0 5 2
    1 3 6
    0 6 -2
    1 1 9

## 输出
    
    
    5
    9

## 说明
    
    
    第一次操作后设备上的能量为：  
    $[4,0,0,3,0,0,2,0,0,1]$  
    第二次操作后设备上的能量为：  
    $[4,0,0,3,2,0,2,1,0,1]$  
    第二次操作后设备上的能量为：  
    $[4,0,0,3,2,-2,2,1,-1,1]$

## 备注:



## 时空限制

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

## 题目描述

小H今天在学校里学习了历史，小H对楚汉争霸的历史非常感兴趣，因此小H决定和同伴们玩一个两国争霸游戏。总共有 $n$ 座城池，两座城池之间可能有道路相连。刚好有 $n-1$ 条道路将所有城池连成了树的形状。每座城池一开始可以被 $A,B$ 两个国家占领，或者是无主的城池 $Z$ ，且一开始每个端点城池（只有一条道路和其他城池相连的城池）都不是无主的。每个国家可以占领与自己城池相连的城池，占领后可以进一步扩张势力，每个国家都希望占领尽可能多的城池，因此任何一座无主城池最终都会被占领。但是小H不希望游戏结束太快，因此希望两个国家势均力敌，小H想知道最终两个国家占领总城池数差最小值是多少？****

## 输入描述:
    
    
    第一行输入正整数 $n$, 表示有 $n$ 座城池。  
    第二行输入 $n$ 个字符 $a_i$, 表示第 $i$ 座城池的所属国家。其中$A,B$ 表示分别属于两个国家, $Z$ 表示这个城池为无主的。  
    接下来 $n-1$ 行，每行三个正整数 $u,v$, 表示 $u$ 城池和 $v$ 城池之间有一条道路。  
    $1≤n≤10^5$  
    $1≤u,v≤n$

## 输出描述:
    
    
    一个非负整数，表示最少两个国家占领总城池数差最小值。若 $|A|,|B|$为最终两国家占领总城池数，请输出 $\lVert|A|-|B|\rVert$。  
    

示例1 

## 输入
    
    
    5
    A Z B A B
    1 2
    2 3
    2 4
    2 5

## 输出
    
    
    1

## 说明


## 备注:



## 时空限制

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