#P4701. 采样
采样
题目背景
“看着我的眼睛。”——优祖列罕
题目描述
VOID 抽取的每个基因是由大写英文字母组成的环状字符串。第 个环状基因的长度为 。从第 个位置顺着环读完一圈,可以得到最初编号为 的链状基因。链状基因的内容可以相同,但它们的编号各不相同。例如,环状基因 ABCAB 的 个链状基因依次为 ABCAB、BCABA、CABAB、ABABC、BABCA。
第 个环状基因还有两个参数 。先给各个编号 设定权重
$$f_i(x)=x-\frac{p_i+t_i+l_i}{2}\ln(x^2+1) +(p_i l_i+p_i t_i-1)(\arctan x+1).$$这里 是自然对数, 的结果以弧度计。只要有两个编号 满足 ,且当前编号 的链状基因字典序小于当前编号 的链状基因,就可以交换这两个链状基因的编号。权重始终与编号绑定。持续交换,直到没有符合条件的编号对。最终采样与合法交换的顺序无关。
取最后编号为 的链状基因作为第 个环状基因的采样 。若 ,且 是 的前缀,则称第 个环状基因是第 个环状基因的亲和体。两个完全相同的采样也满足前缀条件。求每个环状基因拥有的亲和体数量。
输入格式
第一行包含一个整数 ,表示环状基因的数量。
接下来 行,每行包含一个由大写英文字母组成的非空字符串,以及两个整数 。该字符串的长度为 ,且 ,。
输出格式
输出 行,每行一个整数。第 行表示第 个环状基因的亲和体数量。
4
CDEAB 3 2
ABC 2 4
D 1 6
EDEE 2 6
1
0
0
1
样例解释
第 个环状基因各编号的初始链状基因与权重如下。
| 编号 | 初始链状基因 | 的近似值 |
|---|---|---|
| 1 | CDEAB |
|
| 2 | DEABC |
|
| 3 | EABCD |
|
| 4 | ABCDE |
|
| 5 | BCDEA |
依次交换编号 、、,编号 最终对应 ABCDE。四个采样依次是 ABCDE、ABC、D、DEEE,所以第 个基因是第 个的亲和体,第 个基因是第 个的亲和体。