数字之和

题目描述

给定一个数字字符串 n，定义一次操作为：移除字符串中一个非空子串，并将剩余部分拼接形成新数字。
求所有可能操作方案生成的新数字之和，结果对 10⁹+7取模。

输入格式

一行字符串 n

输出格式

一个整数，表示所有方案生成数字之和取模后的结果。

输入样例#1

1003

输出样例#1

339

输入样例#2

123

输出样例#2

52

说明提示

【数据范围】

1≤∣n∣≤10⁵,| n |表示字符串长度。

限制

时间限制：1000ms

内存限制：256MiB

花车巡游

题目描述

嘉年华的花车巡游正在展示精心编排的队列变换！
最初，所有 N辆花车排成一行，花车 i 位于第 i 位。变换程序由 K 个位置对 (a1,b1),(a2,b2),…,(aK,bK) 描述。表演过程中：

· 第 11 分钟：位置 a1​ 与 b1​ 的花车交换位置

· 第 22 分钟：位置 a2​ 与 b2​ 的花车交换位置

· ……

· 第 K 分钟：位置 aK​ 与 bK​ 的花车交换位置

· 第 K+1 分钟：重新从 (a1,b1) 开始交换（即位置 a1​ 与 b1​ 交换）

· 第 K+2 分钟：位置 a2​ 与 b2​ 交换

· 如此无限循环……

请计算每辆花车在整个表演过程中能到达的不同位置数量。

输入格式

第一行输入 N,K。

接下来 KK 行每行包含 ai,bi​（1≤ai<bi≤N）。

输出格式

输出 N行，第 i行为花车 i能到达的不同位置数量。

输入样例

5 4

1 3

1 2

2 3

2 4

输出样例

4

4

3

4

1

说明提示

样例解释

· 花车 11 可到达位置 {1,2,3,4}{1,2,3,4}

· 花车 22 可到达位置 {1,2,3,4}{1,2,3,4}

· 花车 33 可到达位置 {1,2,3}{1,2,3}

· 花车 44 可到达位置 {1,2,3,4}{1,2,3,4}

· 花车 55 始终在位置 55（未移动）

【数据范围】

1≤K≤2×1051≤K≤2×105

2≤N≤1052≤N≤105

限制

时间限制：1000ms

内存限制：256MiB

公平

题目描述

有多干所精英学院和 N 名天才学员（编号 1 到 N）。每名学员 i拥有能力值 Ai​ 和初始所属学院 Bi​。

联盟定期进行学员调院操作（共 Q 次）：第 j次操作将学员 Cj 调到学院 Dj​。

联盟公平指数定义为：

对每所至少有一名学员的学院，取该学院最高能力值；再取这些最高能力值中的最小值。

请计算每次调院操作后的联盟公平指数。

输入格式

· 第一行：NN QQ

· 接下来 NN 行：每行 AiAi​ BiBi​，表示学员 ii 的能力值和初始学院

· 接下来 QQ 行：每行 CjCj​ DjDj​，表示将学员 CjCj​ 调到学院 DjDj​

输出格式

· QQ 行：每行一个整数，表示每次操作后的公平指数

输入样例#1

6 3  

8 1  

6 2  

9 3  

1 1  

2 2  

1 3  

4 3  

2 1  

1 2  

输出样例#1

6  

2  

6  

输入样例#2

2 2  

4208 1234  

3056 5678  

1 2020  

2 2020  

输出样例#2

3056  

4208  

说明提示

1≤N,Q≤2×1051≤N,Q≤2×105
1≤Ai≤1091≤Ai​≤109
1≤Cj≤N1≤Cj​≤N
1≤Bi,Dj≤2×1051≤Bi​,Dj​≤2×105
输入均为整数
每次转园操作会改变所属学院

限制

时间限制：1000ms

内存限制：256MiB

题目描述

给定一棵包含 N个顶点的树。顶点编号为 1 至 N，第 i条边 (1≤i≤N−1) 连接顶点 a_i与顶点 b_i​。

对于树中任意两个顶点 u 和 v（满足 u<v），定义距离 d(u,v)为连接 u 和 v的简单路径上的边的数量。

请计算所有满足 u<v的顶点对 (u,v) 的距离 d(u,v) 的总和。

输入格式

第一行 ，一个整数表示n
接下来的n−1行，每行两个整数ai,bi.

输出格式

输出所有满足 u<v的顶点对 (u,v) 的距离 d(u,v)的总和。

输入样例#1

3

1 2

2 3

输出样例#1

3

输入样例#2

5

1 2

1 3

1 4

1 5

输出样例#2

10

说明提示

【 数据范围 】

· 2≤N≤10⁵

· 1≤a_i,b_i≤N

限制

时间限制：1000ms

内存限制：256MiB