yl-9/probench huggingface dataset:
# 小H学地理

## 题目描述

小H今天在学校里学习了地理，小H了解到我国地大物博，幅员辽阔，于是小H想去游玩一番祖国的大好河山。小H提前制定好了旅游线路计划，包括 $n$ 个旅游景点，景点编号由 1 到 $n$， $m$ 条连接不同景点的路线，其中每个景点都可以通过路线走到。但是小H哪个都想游玩，也不想安排游玩顺序，于是小H决定从景点 1 出发，以相同概率前往相邻的景点，直到游玩到景点 $n$，结束旅行。每个景点最终的游玩乐趣 $c$ 与最终游玩次数 $x$ 有关，且由景点游玩新鲜度 $b$ 和审美疲劳度 $a$ 决定，具体表达式为 $c=bx-ax^2$。  


小H想知道所有景点最终的游玩乐趣的期望值之和是多少，小H提前列好了景点有趣程度和审美疲劳度的个性化列表，但是粗心的小H忘记了标记景点编号，列表上只有 $n$ 条成对信息。因此最终的所有景点最终的游玩乐趣的期望值有多种可能，小H非常乐观，因此他想知道所有可能的期望值之中最大的是多少？ 

**题目保证图是连通的且无重边和自环。**

## 输入描述:
    
    
    第一行输入两个正整数 $n, m$，表示有 $n$ 个景点，$m$ 条路线。  
    接下来 $n$ 行，每行输入两个正整数 $a, b$，表示景点的审美疲劳度和游玩新鲜度。  
    接下来 $m$ 行，每行输入两个正整数 $u, v$，表示景点 $u, v$ 之间有一条线路。  
    $1\leq n \leq300$  
    $0\leq m\leq \frac{n(n-1)}{2}$  
    $1\leq a,b \leq10^5$

## 输出描述:
    
    
    一个浮点数，表示最大可能的期望值，如果答案的绝对误差或相对误差不超过 $10^{-6}$ ，则认为答案正确。  
    形式上，假设你的答案为 $x$，标准答案为 $y$。当且仅当 $\frac{|x-y|}{max(1,|y|)} \leq10^{-6}$ 时，你的答案被认为是正确的。

示例1 

## 输入
    
    
    3 2
    2 7
    1 3
    3 7
    1 2
    2 3

## 输出
    
    
    6.0000000000

## 说明
    
    
    最终游玩次数期望依次为$\lbrace 2,2,1\rbrace$,游玩次数平方期望依次为$\lbrace 6,6,1\rbrace$,  
    此时个性化列表依次为 $\lbrace (2,7),(1,3),(3,7)\rbrace$,总期望值最大

示例2 

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

## 输出
    
    
    -0.8888888889

## 说明
    
    
    最终游玩次数期望依次为$\lbrace \frac{4}{3},\frac{2}{3},1\rbrace$,游玩次数平方期望依次为$\lbrace \frac{20}{9},\frac{10}{9},1\rbrace$,  
    此时个性化列表依次为 $\lbrace (1,1),(3,2),(5,7)\rbrace$,总期望值最大

## 备注:



## 时空限制

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

## 题目描述

给定两个整数 $x,y$，jackle 希望把 $x$ 变成 $y$。 

  


他每次可以进行如下两种操作之一：  


  * 选择任意一个整数 $z$，令 $x=x\ \&\ z$。 
  * 选择任意一个整数 $z$，令 $x=x\ |\ z$。 



  


请问最少操作几次可以把 $x$ 变成 $y$。

## 输入描述:
    
    
    本题有多组测试数据。  
      
    第一行输入 $1$ 个正整数 $T(1\leq T\leq 10^5)$ ，表示数据组数。  
      
    接下来 $T$ 行，每行 $2$ 个整数 $x,y(0\leq x,y\leq 10^{18})$。

## 输出描述:
    
    
    对于每组测试数据，输出最少操作次数。

示例1 

## 输入
    
    
    2
    0 0
    0 1

## 输出
    
    
    0
    1


## 时空限制

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

Difficulty: 500
# 闯关

## 题目描述

一个骑士在进行闯关，面前有 $n+1$ 个房间：$0,1,2,...,n$，他**初始在** $0$**号房间** ，他需要按顺序通过房间。  
  
从 $1$ 号房间开始，每个房间有个数值 $a_i$，若 $a_i\ge0$ 则，骑士进入之后会恢复 $a_i$ 的血，否则进入会扣除 $-a_i$ 的血。  
  
骑士每走一步，都会前进一个房间，若骑士在某一时刻的血量 $\leq 0$，则死亡，无法继续闯关。  
  
现在骑士有 $h$ 的初始血量，jackle 想让你构造一个长度为 $n$ 的 $a$ 序列，满足 $L\leq a_i\leq R$，且骑士恰好走 $k$ 步之后死亡。

## 输入描述:
    
    
    在一行输入 $5$ 个整数 $n,k,h,L,R(1\leq k\leq n\leq 10^5,1\leq h\leq 10^9,-10^9\leq L\leq R\leq 10^9)$，分别表示序列长度，恰好走的步数，初始血量，以及两个边界参数。

## 输出描述:
    
    
    如果无法构造请输出 impossible。
    
    否则在一行输出 $n$ 个整数，表示任意一组合法解。

示例1 

## 输入
    
    
    2 1 3 -4 0

## 输出
    
    
    -3 -4

示例2 

## 输入
    
    
    2 2 1 -1 -1

## 输出
    
    
    impossible


## 时空限制

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

Difficulty: 1000
# f * g

## 题目描述

给定两个长度为 $n$ 的序列 $f,g$。 

  


定义 $V=\sum_{i=1}^n\sum_{j=1}^nf_{\min(i,j)}\times g_{\max(i,j)}$  


  


同时有 $Q$ 次操作： 

  * $1,i,x$：令 $f_i=x$ 


  * $2,i,x$：令 $g_i=x$ 



**  
**

**注意每次修改不是独立的，本次修改会影响后续的询问。**

  


jackle 想让你告诉他每次操作之后 $V$ 的值是多少？ 

  


由于答案很大，请输出答案对 $998244353$ 取模之后的结果。

## 输入描述:
    
    
    第一行输入 $2$ 个正整数 $n,Q(1\leq n,Q\leq 1\times 10^5)$，分别表示序列长度，操作次数。  
      
    第二行输入 $n$ 个正整数 $f_i(1\leq f_i\leq 10^9)$。  
      
    第三行输入 $n$ 个正整数 $g_i(1\leq g_i\leq 10^9)$。  
      
    接下来 $Q$ 行，每行输入三个整数 $t,i,x$，其中 $t\in \{1,2\}$，$1\leq i\leq n$，$1\leq x\leq 10^9$。

## 输出描述:
    
    
    输出 $Q$ 行，每行一个整数，表示本次操作结束之后 $V$ 的值是多少。**（答案对** $998244353$**取模）**

示例1 

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

## 输出
    
    
    41
    55
    60

示例2 

## 输入
    
    
    3 2
    1 1 1
    2 2 2
    1 1 3
    2 2 9

## 输出
    
    
    38
    87


## 时空限制

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

Difficulty: 1500
# 最好的序列（Easy）

## 题目描述

**注意区分本题的 Easy 和 Hard 版本，两个版本问的问题不是一样的！！**

**  
**

称满足如下条件的序列 $a$ 是 “好序列”：

  * $\forall i\in[1,n]$，$1\leq a_i\leq X$。 
  * $LCM(a_1,a_2,...,a_n)\leq Y$。 



  


在所有 “好序列” 中，序列中**未出现的最小正整数最大****的** 序列称为 "最好的序列"。

  


请问在所有 ”最好的序列“ 中，$LCM(a_1,a_2,...,a_n)$ 的最大值是多少？ 

## 输入描述:
    
    
    本题有多组测试数据。  
      
    第一行输入一个整数 $T(1\leq T\leq 2\times 10^4)$，表示数据组数。  
      
    接下来 $T$ 行，每行输入 $3$ 个整数 $n,X,Y(1\leq n,X,Y\leq 10^{14})$。

## 输出描述:
    
    
    对于每组测试数据，输出在所有 ”最好的序列” 中， $LCM(a_1,a_2,...,a_n)$ 最大值。

示例1 

## 输入
    
    
    6
    1 7 23
    2 3 112
    33 44 55
    32 111 22132
    4444 2222 2222222
    23 26 998244353

## 输出
    
    
    1
    2
    48
    20160
    2162160
    232792560


## 时空限制

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

Difficulty: 2300
# 三叶草

## 题目描述

给定一棵 $n$ 个节点的无根树，每个节点都有一种颜色 $col_i$（黑或者白）。 

  * 若存在 $a,b,c,d$ 这 $4$ 个不同的节点满足 $col_b=col_c=col_d$ ， $col_a\not=col_b$，且 $a$ 与 $b,c,d$ 均有邻边，则称 $a,b,c,d$ 构成了一片三叶草。 



你至多有 $k$ 次修改，每次修改可以改变一个节点的颜色（黑 $\to$ 白 或者 白 $\to$ 黑），请问树上最多可以构成多少片三叶草。

## 输入描述:
    
    
    第一行输入 $2$ 个整数 $n,k(1\leq n\leq 350,0\leq k\leq n)$，分别表示树的大小，最多修改的次数。  
      
    第二行输入 $n$ 个数 $col_i$，表示每个节点的颜色（$col_i=0$ 表示白色，$col_i=1$ 表示黑色）。  
      
    接下来 $n-1$ 行，每行输入两个正整数 $u,v(1\leq u,v\leq n)$，表示 $u$ 与 $v$ 之间有一条边。

## 输出描述:
    
    
    请你输出树上最多可以构成多少片三叶草。

示例1 

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

## 输出
    
    
    1

## 说明
    
    
    可以把 $col_4$ 改为 $0$，这样 $1,2,3,4$ 构成了一片三叶草。

示例2 

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

## 输出
    
    
    5

## 说明
    
    
    ![](https://uploadfiles.nowcoder.com/images/20241014/0_1728898105130/0717EC68D7E5690BCF2DFB02D4C9CB14)
    
    一种能使得三叶草数量达到最大值的操作方式如下：
    
    改变 $3,7$ 节点的颜色，最终树上的三叶草有：$\{1,2,3,4\}$，$\{1,2,3,5\}$，$\{1,3,4,5\}$，$\{1,2,4,5\}$，$\{4,1,7,8\}$，一共 $5$ 个。


## 时空限制

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

Difficulty: 2400
# 最好的序列（Hard）

## 题目描述

**注意区分本题的 Easy 和 Hard 版本，两个版本问的问题不是一样的！！**  


**  
**

称满足如下条件的序列 $a$ 是 “好序列”： 

  * $\forall i\in[1,n]$，$1\leq a_i\leq X$。 
  * $LCM(a_1,a_2,...,a_n)\leq Y$。 



  


在所有 “好序列” 中，序列中**未出现的最小正整数最大****的** 序列称为 "最好的序列"。 

  


请问有多少种不同的 “最好的序列” ，答案对 $998244353$ 取模。 

## 输入描述:
    
    
    本题有多组测试数据。  
      
    第一行输入一个整数 $T(1\leq T\leq 2\times 10^4)$，表示数据组数。  
      
    接下来 $T$ 行，每行输入 $3$ 个整数 $n,X,Y(1\leq n,X,Y\leq 10^{14})$。

## 输出描述:
    
    
    对于每组测试数据，输出有多少种不同的 “最好的序列”。

示例1 

## 输入
    
    
    4
    2 4 6
    4 10 29
    123 456 789
    20 20 301027

## 输出
    
    
    2
    24
    462553434
    511292827

## 说明
    
    
    第一组样例：答案序列可以为 $\{1,2\}$ 或者 $\{2,1\}$，其最小未出现的正整数都是 $3$，这是所有最好的序列中最小未出现的正整数最大的，且 $LCM(1,2)=2\leq 6$。


## 时空限制

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

Difficulty: 2400
# 数数

## 题目描述

牛牛穿越到了异世界。  
  
在异世界中，牛牛发现这里的人们对奇数和偶数有着独特的定义，在这里，奇数被定义为只有一个质因数的数（相同的质因数不被重复计算），偶数定义为质因数个数大于 $1$ 的数，$1$ 既不是奇数也不是偶数 。牛牛想要知道 $1$ ~ $n$ 中偶数的个数，聪明的你能帮牛牛解决这个问题吗？  
  
例如：$2 = 2 ^ 1$ 是奇数，$8 = 2 ^ 3$ 是奇数，$45 = 3^2\times5$ 是偶数。

## 输入描述:
    
    
    输入一个整数 $n(1\leq n\leq 5*10^6)$。

## 输出描述:
    
    
    输出一个整数表示答案。

示例1 

## 输入
    
    
    5

## 输出
    
    
    0

示例2 

## 输入
    
    
    6

## 输出
    
    
    1


## 时空限制

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

Tags: 思维
Difficulty: 600
# 三位出题人

## 题目描述

三位出题人走在路上，他们要给 $m$ 个人分配 $n$ 个题的工作，第一位出题人认为不应该让所有人同时去参与同一个题的工作，第二位出题人认为每个题都应该有至少一个人参与，第三位出题人认为可以有人不分配到任何题目。 

  


你想知道他们有多少种分配任务的方案。 

  


注意一个人可以被分配多个题目的工作，一个题目可以不止有一个人负责。 

## 输入描述:
    
    
    第一行一个整数 $T$ $(1\leq T\leq 100)$。  
      
    接下来 $T$ 行，每行两个整数 $n, m$ $(1\leq n, m\leq 10^{6})$。

## 输出描述:
    
    
    共 $T$ 行，每行一个整数表示答案，并对 $10^9 + 7$ 取模。

示例1 

## 输入
    
    
    2
    1 3
    100 3

## 输出
    
    
    6
    876928896


## 时空限制

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

Tags: 筛法, 数论
Difficulty: 900
# 和天下

## 题目描述

Panjy 在玩维多利亚 3，他在游戏里统一了世界，他觉得统一天下没有难度，于是想让你做一道题。 

  


给定一个长度为 $n$ 的序列 $a$，你有一张大小为 $n$ 的图 $G$，$G$ 满足对于两个不同整数 $1\le u,v\le n$，若 $a_u \odot a_v \ge k$，则 $u, v$ 之间存在一条边，反之不存在边。 

  


求该图最大连通块的点数。其中 $\odot$ 为按位与运算。 

  


  


## 输入描述:
    
    
    第一行一个整数 $T$ 表示数据组数。  
      
    对于每组数据，第一行输入两个正整数 $n, k$ $(1\le n\le 2\times 10^5, 0\le k\le 10^{18})$，分别表示序列长度及连边最小按位与值。  
      
    第二行输入 $n$ 个正整数分别为 $a_1,a_2,...,a_n$ $(0\le a_i\le 10^{18})$。  
      
    保证 $\sum n\le 2\times 10^5$。

## 输出描述:
    
    
    对于每组数据，输出一个整数，表示最大连通块的大小。

示例1 

## 输入
    
    
    2
    5 1
    5 21 1 8 10
    5 4
    5 3 7 10 15

## 输出
    
    
    3
    4


## 时空限制

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

Tags: 数据结构, 并查集, 枚举, 位运算
Difficulty: 1800
# 搬家

## 题目描述

给定 $n$ 个物品，$m$ 个收纳箱，物品和收纳箱均排成一行，每个收纳箱容量均为 $k$，每个物品体积为 $a_i$。 

  


初始指定第一个收纳箱，并选择一个起始位置 $i$，从第 $i$ 个物品开始按顺序遍历它和它右侧的所有物品，对于每一个遍历的物品： 

  1. 如果当前物品可以装入目前指定的收纳箱，则将其装入。 
  2. 反之则指定其右侧的第一个收纳箱，重复第一步。 
  3. 直到物品被遍历完，或者右侧不存在收纳箱时，停止过程。 



问能最多装入多少物品。 

## 输入描述:
    
    
    第一行一个整数 $T$，表示数据组数。  
      
    对于每组数据，第一行三个整数 $n, m, k$ $(1\leq n, m\leq 10^5, 1\leq k\leq 10^9)$。  
      
    接下来一行 $n$ 个整数 $a_i$ $(1\leq a_i\leq k)$。  
      
    保证 $\sum n, m\leq 10^5$。  
    

## 输出描述:
    
    
    输出 $T$ 行，每行一个整数表示最多能装入多少物品。

示例1 

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

## 输出
    
    
    3

## 说明
    
    
    从第 $1$ 个物品开始选，第 $1$ 个盒子装第 $1$ 个物品和第 $2$ 个物品，第 $2$ 个盒子装第 $3$ 个物品。  
      
    从第 $2$ 个物品开始选，第 $1$ 个盒子装第 $2$ 个物品，第 $2$ 个盒子装第 $3$ 个物品。  
      
    从第 $3$ 个物品开始选，第 $1$ 个盒子装第 $3$ 个物品，第 $2$ 个盒子装第 $4$ 个物品。  
      
    从第 $4$ 个物品开始选，第 $1$ 个盒子装第 $4$ 个物品，第 $2$ 个盒子装第 $5$ 个物品。  
      
    从第 $5$ 个物品开始选，第 $1$ 个盒子装第 $5$ 个物品。  
      
    所以最多装 $3$ 个物品。

示例2 

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

## 输出
    
    
    4

## 说明
    
    
    从第 $1$ 个物品开始选，第 $1$ 个盒子装第 $1$ 个物品和第 $2$ 个物品，第 $2$ 个盒子装第 $3$ 个物品和第 $4$ 个物品。  
      
    从第 $2$ 个物品开始选，第 $1$ 个盒子装第 $2$ 个物品和第 $3$ 个物品 ，第 $2$ 个盒子装第 $4$ 个物品。  
      
    从第 $3$ 个物品开始选，第 $1$ 个盒子装第 $3$ 个物品和第 $4$ 个物品，第 $2$ 个盒子装第 $5$ 个物品。  
      
    从第 $4$ 个物品开始选，第 $1$ 个盒子装第 $4$ 个物品，第 $2$ 个盒子装第 $5$ 个物品。  
      
    从第 $5$ 个物品开始选，第 $1$ 个盒子装第 $5$ 个物品。  
      
    所以最多装 $4$ 个物品。


## 时空限制

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

Tags: 倍增
Difficulty: 1800
# Alice and Bod

## 题目描述

$Alice$ 和 $Bob$ 正在玩一个最近兴起的游戏，名为死亡对称，一人进攻一人防守，进攻方可以进攻 $m$ 次，$m$ 次后如果防守成功则防守方获胜，否则进攻方获胜。  
  
$Alice$ 防守，$Bob$ 进攻。  
  
具体规则如下，给定一个长度为 $n$ 的字符串，进攻方 $Bob$ 每次可以进行如下两种操作的一种。  
  


  1. **_1 l r_** 向 $Alice$ 询问一段字符串的子串 $s[l, r]$ 是否是对称的，即要求 $s_{l + i} = s_{r - i} (0 \leq i \leq r - l)$。 
  2. **_2 l r x_** 将给定字符串的子串 $s[l, r]$ 一段的每个字符同时变成它在字典序中后面的第 $x$ $(0 \le x \le 10^9)$ 个字符，并且规定 $z$ 在字典序中后面的第 $1$ 个字符为 $a$。  


  
$Alice$ 很想赢得这个游戏，但是他对于字符串一窍不通，希望得到你的帮助，在每次询问时做出正确的答案。

## 输入描述:
    
    
    第一行输入两个整数 $n(1\le n \le 10^5)，m(1\le m \le 10^5)$ 分别表示字符串的长度和进攻次数。  
      
    第二行输入一个长度为 $n$ 的字符串 $s$，保证全部由小写字母构成。  
      
    接下来输入 $m$ 行，每行表示一个操作。

## 输出描述:
    
    
    对于每次 $Bob$ 的第一种进攻，若是对称的则输出 YES ，否则输出 NO。

示例1 

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

## 输出
    
    
    NO
    YES
    YES

## 说明
    
    
    第一次操作时，字符串为 $aaz$ ，子串 $s[1...3]$ ，为 $aaz$ ， 并不对称，输出NO
    
    第二次操作，字符串变为 $aaa$
    
    第三次操作时，字符串为 $aaa$ ，子串 $s[1...2]$ 为 $aa$ ，对称，输出YES
    
    第四次操作，字符串变为 $bbb$ 
    
    第五次操作，字符串为 $bbb$ ，子串 $s[1...3]$ ，为 $bbb$ ，是对称的，输出YES


## 时空限制

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

Tags: 数据结构, 线段树
Difficulty: 2400
# 网络通路

## 题目描述

你是 X 国的总工程师，X 国的 $n$ 个城市之间要架设网络通路，使得每两个国家之间可以通过网络相互到达。为了方便，你希望 X 国架设的网络通路数量最多为 $n - 1$。然而 X 国的网络通路技术并不成熟，传输速度可以被感知出来，对于每条网络通路，其传输数据所需时间为 $d_i$，每两条网络通路之间的衔接时间忽略不计。为了使得城市居民使用网络效率最高，你希望对于每两个城市传输时间的和最小，现在你的任务就是求得这个最小值是多少。

## 输入描述:
    
    
    第一行两个整数 $n, m$ $(1\leq n \leq 16, 1\leq m\leq 200)$，接下来 $m$ 行每行两个整数 $u_i, v_i, d_i$ $(1\leq u_i, v_i\leq n, 1\leq d_i\leq 100)$ 表示一条边。不保证没有重边和自环。

## 输出描述:
    
    
    第一行一个整数 $ans$ 表示答案，若不存在使得每两个城市都互相到达的方案，输出 $-1$。

示例1 

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

## 输出
    
    
    10


## 时空限制

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

Tags: 数据结构, 树, 动态规划, 树形dp
Difficulty: 2500
# Cidoai的幂次序列

## 题目描述

给定 $n,k$，你需要构造一个长为 $m$ 的正整数序列 $a$，满足 $2 \le m \le k,\sum_{i=0}^{m-1} a_i^{a_{(i+1) \bmod m}}=n$。

（注：右上角为 $a_{(i+1)\bmod m}$，取模符号在下标处。）

你需要保证对于所有 $a_i$ 都有 $0< a_i \le n$。

## 输入描述:
    
    
    一行两个正整数分别表示 $n,k$。

## 输出描述:
    
    
    第一行输出一个正整数 $m$ 表示序列 $a$ 的长度。  
    第二行 $m$ 个正整数按顺序表示 $a_0,a_1,\dots,a_{m-1}$。

示例1 

## 输入
    
    
    2244 5

## 输出
    
    
    3
    2 3 7

## 备注:
    
    
    对于所有数据，$2 \le n \le 10^{18},2 \le k \le 10^6$


## 时空限制

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

Tags: 思维
Difficulty: 300
# Cidoai的平均数对

## 题目描述

给定 $n$ 对数 $(a_i,b_i)$ 和参数 $k$，你需要选出一些对使得在满足 $b_i$ 的平均值不超过 $k$ 的同时，$a_i$ 的和最大，求出这个最大值。

## 输入描述:
    
    
    第一行两个整数分别表示 $n,k$。  
    接下来 $n$ 行，每行两个数分别表示 $a_i,b_i$  
    

## 输出描述:
    
    
    一行一个整数表示答案。

示例1 

## 输入
    
    
    5 6
    4 10
    3 4
    6 7
    7 7
    10 8

## 输出
    
    
    16

## 备注:
    
    
    $0 \le a_i,b_i,k \le 500,1 \le n \le 500$


## 时空限制

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

Tags: 背包问题, 动态规划
Difficulty: 1100
# Cidoai的树上方案

## 题目描述

给定大小为 $n$ 的有标号有根树，以 1 为根，求在树外引出一个点向树内任意连边使得构成的**简单图** 不含**三元环** 的方案数。答案对 $998244353$ 取模。

## 输入描述:
    
    
    第一行一个正整数 $n$。  
    第二行 $n-1$ 个正整数，分别表示 $p_2,p_3,\dots,p_n$，为 $2,3,\dots,n$ 节点的父亲节点编号。  
    

## 输出描述:
    
    
    一行一个整数表示答案

示例1 

## 输入
    
    
    6
    1 1 2 2 3

## 输出
    
    
    23

## 备注:
    
    
    $n \le 2\times 10^6$，保证 $\forall 2 \le i \le n, p_i < i$


## 时空限制

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

Tags: 动态规划, 树形dp
Difficulty: 1400
# Cidoai的字符集合

## 题目描述

Cidoai 听到了 $n$ 首歌。每首歌都有一个旋律长度，第 $i$ 首歌的长度为 $k_i$，旋律序列为一个长度为 $k_i$ 的仅由小写字母组成的单词序列。  
  
他认为这些歌中有一些是相似的。他定义两首歌 $x,y$ 相似当且仅当这两首歌中存在至少一个旋律是相同的，即至少一个单词是相同的，记作 $x \sim y$。  
  
你需要为他求出这 $n$ 首歌最少可以被划分成多少个集合，使得每个集合 $S$ 都满足：$\forall u \in S, \exists v \in S, u \neq v, u \sim v$ 或 $|S|=1$  


## 输入描述:
    
    
    第一行一个正整数 $n$。  
    接下来 $n$ 行，每行第一个整数 $k_i$ 表示歌曲 $i$ 的旋律长度，接下来 $k_i$ 个字符串表示歌曲 $i$ 中的旋律。  
    

## 输出描述:
    
    
    一行一个整数表示答案。

示例1 

## 输入
    
    
    3
    3 ababc ccaab ccbab
    4 ababa ccbab abcab dbacd
    3 aabbcd abcad ddacb

## 输出
    
    
    2

示例2 

## 输入
    
    
    10
    10 yanafrrtqd kvupeclkau ccmilushkl jprneeifaa mfvxrpkiku jelcmrfgcb ugcyggbtyc fcwcmovwab bbokcijkhr wbucibwpxs
    10 colojsdmfb kvifvnluiu ujgvrfjznt piupliwdum hxnaqlkmjn vyroklirhk ywvdvnhufy finvhstpax dpkuorlaro ynybgehzsl
    10 gatncocjvb bzxgwlhtgt wlxfcvnnmy ohxgxmfqaf enekeahjkc hibbabuqfv wsrgzsjvzf kdrpfxjvhm junrbhnjmd xnsjifazhm
    10 zwazrlklra mricnjqfcc ubphalodyh ywrgnltzbm ammknyfffh ncvqbwjiof dtenyzvhtr qtwjinnvdj gcmssbgmma oeqtyxhbon
    10 whvzszoekn rvxtxygeiw nxwofrsovq ghdeciwqou anlhigwubx eohknpcqrz rwaasmgqkn frkluphzhj xrllcuhwvv ipftevlujd
    10 omhaaflhah okkipqvdup hxnaqlkmjn fjpxhdzifv gxvbpbvbzx hghuizfjmk lwllhmyjdc hrwncsqbri qetxuqkjps gzfyrmwton
    10 eqwwhpuoaq lwaqpciksx gfipvjkbyh hotojhhzmy uqkhzkceud bqjamjebad ysijhzgtpk vwrcsppumx gyxspyvtdt ufoeprnvuj
    10 hxtvczmfng oymzqvbsak chzyqpbarb qveytprqwu ompsalmrwp bcwzqzaosi giputlgekx qcfvzdizyh tqywmcxivp ugzvukersa
    10 sdzxwnqiwc mhygxxiaxa vfykioxawf txodxyiplw tzmqjtjvlv atbonqcyrw stigqwzebp nskzejfryi qxbqejmoae lzldylftzk
    10 zvhwzrxeyy ksskesehze wadmkrvldb dofrbephlz scniotunqn povbjbexqz eqvisgsrnv wpmxclmuzd bgafvpzwmx aahqfcogkc

## 输出
    
    
    9

示例3 

## 输入
    
    
    10
    3 j e j
    3 n h d
    3 o p n
    3 b n w
    3 s a q
    3 m t x
    3 w u x
    3 z p m
    3 r t q
    3 f e u

## 输出
    
    
    1

## 备注:
    
    
    记所有字符串总长为 $L$。对所有数据，$n \le 10^6,L \le 10^6$。字符串仅由小写字符构成。


## 时空限制

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

Tags: 图论, 连通性
Difficulty: 2300
# Cidoai的映射数列

## 题目描述

给出两个整数 $n,k$，有一个正整数集合 $X=\\{1,2,3,\cdots,n-1,n\\}$。你需要求出满足以下条件的映射 $f: X \to X$ 的个数模 $998244353$ 的值：  
  


  * $f \circ f=I_X$，即 $f(f(x))=x$ 

  


  * $|f(x)-x| \le k$ 

  
多组询问。

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

## 输出描述:
    
    
    对于每组询问给出一个整数表示答案。

示例1 

## 输入
    
    
    3
    1 2
    2 2
    10 2

## 输出
    
    
    1
    2
    401

示例2 

## 输入
    
    
    17
    139754416593073275 0
    833765607755589325 1
    185041629421702226 1
    953031153271052631 4
    786720619080856843 5
    577621338034224248 7
    675652244815921328 1
    231244666266874950 6
    240969306492599296 5
    509638228083054282 4
    593821090139623660 3
    816334807743313535 7
    619044893793794333 4
    374611401577643223 7
    232433692850847851 3
    453644240040088758 3
    325789550856755047 7

## 输出
    
    
    1
    582941273
    280129160
    136060256
    779006836
    97870039
    95557880
    68654365
    811083393
    978374457
    112909173
    911189580
    197634020
    514851466
    231182803
    820857264
    126377224

## 备注:
    
    
    $1 \le T \le 500,1 \le n \le 10^{18},0 \le k \le 7$


## 时空限制

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

Tags: 线性代数, 矩阵乘法, 数论
Difficulty: 2300
# Cidoai的数论求和

## 题目描述

求 $\sum_{i=1}^n\sum_{j=1}^{n}\sum_{k=1}^n[\gcd(i,j,k)=1][ij=k(i-j)]$ 其中 $\gcd$ 表示最大公约数，$[]$ 表示艾弗森括号，若括号内命题为真，它的值为 $1$，否则为 $0$。

## 输入描述:
    
    
    一行一个正整数 $n$。

## 输出描述:
    
    
    一行一个整数表示答案。

示例1 

## 输入
    
    
    10

## 输出
    
    
    3

示例2 

## 输入
    
    
    1000000

## 输出
    
    
    421389

示例3 

## 输入
    
    
    10000000000

## 输出
    
    
    4213829685

## 备注:
    
    
    $n \le 10^{13}$


## 时空限制

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

Tags: 数学, 莫比乌斯反演, 数论
Difficulty: 2400
# 小红的最大价值

## 题目描述

小红有一个长度为 $n$ 的数组，定义一个数对的 $a_i, a_j, i < j$ 的价值为：如果 $|a_i - a_j| > k$，则价值为 $\max(a_i, a_j)$，否则价值为 $\min(a_i, a_j)$。  
小红想知道所有数对的最大价值是多少。

## 输入描述:
    
    
    第一行两个整数 $n, k$，表示数组长度和常数 $k$。  
    第二行 $n$ 个整数 $a_i$，表示数组的元素。  
    $2 \leq n \leq 10^5$  
    $1 \leq a_i, k \leq 10^9$

## 输出描述:
    
    
    输出一个整数，表示所有数对的最大价值。

示例1 

## 输入
    
    
    5 3
    1 2 3 4 5

## 输出
    
    
    5

## 说明
    
    
    选择 $a_1 = 1, a_5 = 5$，$|1 - 5| = 4 > 3$，价值为 $5$。


## 时空限制

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

Tags: 贪心
Difficulty: 300
# 小红的约数

## 题目描述

对于一个正整数 $n$ 和一个非负整数 $d$，定义 $f_d(n)$ 为 $n$ 的所有约数的 $d$ 次方之和。如 $f_3(10) = 1^3 + 2^3 + 5^3 + 10^3$。  
  
现给定 $n, d$，求 $f_d(n)$ 的值。由于答案可能很大，输出答案对 $10^9 + 7$ 取模的结果。

## 输入描述:
    
    
    由于 $n$ 可能很大，所以给出 $n$ 的质因数分解式。  
    $n = \prod_{i = 1}^w p_i^{a_i}$  
      
    第一行输入一个正整数 $w$ 和一个非负整数 $d$。  
    接下来 $w$ 行，每行输入两个正整数 $p_i, a_i$。  
    保证 $p_i$ 为素数且互不相同。  
      
    对于全部的测试点，保证 $1 \leq w \leq 10^5, 0 \leq d \leq 10^9, 2 \leq p_i \leq 10^9, 1 \leq a_i \leq 10^9$。

## 输出描述:
    
    
    输出$f_d(n)$对 $10^9 + 7$ 取模的结果。

示例1 

## 输入
    
    
    2 3
    2 1
    5 1

## 输出
    
    
    1134

## 说明
    
    
    $f_3(10) = 1^3 + 2^3 + 5^3 + 10^3 = 1134$。


## 时空限制

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

Tags: 数论
Difficulty: 1200
# 小红的图上划分

## 题目描述

小红有一个无向图，有 $n$ 个点 $m$ 条边。小红有 $q$ 个询问，每次给出 $L, R$，求将图划分为至少 $L$ 个连通块，最多 $R$ 个连通块的最大划分价值，若不可划分输出 "NO ANSWER"。  
  
图的划分定义为将图划分为一个或多个连通块，对于每个连通块，其点集为其边集中每一条边的两端点的集合，且点集内任意两点均可通过边集里的边互相到达。  
  
划分价值定义为所有连通块边集中的最小边权。

## 输入描述:
    
    
    第一行输入三个整数 $n, m, q$，表示点数，边数，询问数。  
    接下来 $m$ 行，每行三个整数 $u, v, w$，表示一条边，连接 $u, v$，边权为 $w$。  
    接下来 $q$ 行，每行两个整数 $L, R$，表示询问。  
    对于全部测试点，保证   
    $1 \leq n, m \leq 2 \times 10^5$  
    $1 \leq q \leq 2 \times 10^5$  
    $1 \leq u, v \leq n$  
    $-10^9 \leq w \leq 10^9$  
    $1 \leq L \leq R < n$

## 输出描述:
    
    
    输出 $q$ 行，表示对应询问的答案。

示例1 

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

## 输出
    
    
    NO ANSWER
    2

## 说明
    
    
    第一个询问，选取所有边也只有 2 两个联通块，无法满足条件。  
    第二个询问，选取第 2,3,4 条边，有两个联通块，边集中最小边权为 2，不存在更大的划分价值。  
    
    
      
    


## 时空限制

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

Tags: 图论, 生成树, 连通性
Difficulty: 1600
# 小红的白点距离

## 题目描述

小红有一棵树，初始所有点都是白色。小红最多可以染黑 $k$ 个点，定义染色后树的权值为白色点对距离的最大值，求最小的权值。

## 输入描述:
    
    
    第一行输入两个整数 $n, k$，表示树的点数和最多染黑点数。  
    接下来 $n-1$ 行，每行输入两个整数 $u, v$，表示树上的一条边。  
    $3 \leq n \leq 1000$  
    $0 \leq k \leq n - 2$  
    $1 \leq u, v \leq n$

## 输出描述:
    
    
    输出一个整数，表示最小的权值。

示例1 

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

## 输出
    
    
    3

## 说明
    
    
    染黑 6 号点即可。


## 时空限制

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

Tags: 图论, 网络流, 数据结构, 树, 二分, 分治, 动态规划, 树形dp
Difficulty: 2200
# 小红的无向图变身

## 题目描述

小红有一个 $n$ 个点的完全无向图，你可以将每条边 $(u, v)$ 变成四种边之一：  
\- 有向边 $(u \to v)$  
\- 有向边 $(v \to u)$  
\- 蓝色无向边  
\- 红色无向边  
并且你需要保证：  
\- 新图不存在至少包含一条有向边的环；  
\- 不存在蓝色四元环（$A,B,C,D$），如图一，其中 $A,B,C,D$ 互不相同；  
\- 不存在红色结构（$A,B,C,X,Y,Z$），如图二，其中 $A,B,C,X,Y,Z$ 互不相同。  
![](https://uploadfiles.nowcoder.com/images/20240626/0_1719390175846/2D01E09D879325A51014F16A2AF905CF)  


定义图上一个的环是一个顶点序列$\\{v_1,v_2, \dots,v_k,v_{k+1}\\}$, 满足$v_1$到$v_k$这$k$个顶点两两不同，并且$v_{k+1} =v_1$,并且对于$i$等于$1$到$k$，边$(v_i,v_{i+1})$要么是一条无向边，要么是一条$v_i$ 指向$v_{i+1}$的有向边。  


小红想知道有多少种方案可以满足上述条件。 

## 输入描述:
    
    
    第一行一个整数 $n$，表示无向图的点数。  
    $(2 \leq n \leq 5 \times 10^5)$

## 输出描述:
    
    
    输出一个整数，表示答案对 $998244353$ 取模的结果。

示例1 

## 输入
    
    
    2

## 输出
    
    
    4

## 说明
    
    
    一共有 1 条边，可以把这条边变成 4 种边之一。

示例2 

## 输入
    
    
    3

## 输出
    
    
    26


## 时空限制

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

Tags: 数学, 多项式, 图论, 动态规划
Difficulty: 2400
# 小红的基环树

## 题目描述

小红有一棵基环树，树上有 $n$ 个节点，编号为 1 到 $n$。  
求树上最大的下标之差不超过$k$的两点简单路径长度。简单路径定义为不经过重复边，其长度定义为路径上的边权异或和。  
基环树：$n$个点$n$条边的无向连通图。  


## 输入描述:
    
    
    第一行两个整数$n,k(2\leq n\leq 2\times 10^5,1\leq k< n)$表示基环树的点数。  
    随后$n$行每行三个数$u,v,w(1\leq u,v \leq n, 1\leq w\leq 10^9)$表示一条基环树上的边，保证不存在自环，该图是一个合法的基环树。

## 输出描述:
    
    
    输出一个整数，表示树上路径权值的最大值。

示例1 

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

## 输出
    
    
    15


## 时空限制

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

Tags: 数据结构, 树, 字典树（Trie树）, 字符串
Difficulty: 2400
# 金条切割

## 题目描述

相信你一定接触过下面这个脑筋急转弯：  
  
![](https://uploadfiles.nowcoder.com/images/20241220/0_1734625828953/7A54505A633C4530FD71351A16B53F24)  
  
那么现在小灰灰计划考察小蓝一个类似的问题。  
  
小灰灰总共会提出 $t$ 个问题，第 $i$ 个问题给出两个参数 $len_i$ 和 $m_i$，代表小蓝有一块包含 $len_i$ 个单位的金条，她需要支付工人接下来 $m_i$ 天的工资，要求是工人每天手中能够增加 $1$ 个单位的金条（也就是说允许工人归还金条，进行“找零”操作）。  
  
对于每个问题，小蓝需要回答至少需要切割金条多少次才能够支付工人接下来 $m_i$ 天的工资，使得第 $j$ 天时工人手上能够具有 $j$ 个单位的金条。

## 输入描述:
    
    
    第一行一个正整数 $t$，代表问题个数。  
      
    接下来 $t$ 行，第 $i$ 行包含两个空格分隔的整数 $len_i$ 和 $m_i$。  
      
    保证：  
    $1 \le t \le 10^5$  
    $2 \le len_i \le 10^9$  
    $1 \le m_i \le len_i$

## 输出描述:
    
    
    输出共 $t$ 行，第 $i$ 行输出一个整数代表第 $i$ 个问题的答案。

示例1 

## 输入
    
    
    4
    2 1
    7 7
    9 7
    14 10

## 输出
    
    
    1
    2
    3
    3


## 时空限制

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