#1897. 比赛
比赛
比赛
题目描述
第三试比赛(match) IOI2025 中国国家集训队集中培训 比赛(match) 【题目描述】 有n 名选手,编号分别为1, 2, · · · , n。编号为i 的选手的实力值为i。所有选手分 为红、蓝两队,其中编号为i 的选手所在的队伍用字符si 描述。si 为R 表示他在红队, si 为B 表示他在蓝队。 现在将所有选手排成一个环,每一对相邻且不属于同一队的选手会进行一场比赛, 实力值较大的选手获胜,他所在的队伍的得分增加一。 然而蓝队的选手勾结了裁判,如果一场比赛中.红.队.选.手获胜,且他在蓝队选手的.顺 .时.针.方.向,则这场比赛.不.计.入.得.分。 现在你想知道,对于每个k = −n, · · · , −1, 0, 1, · · · , n,有多少种将选手排列的方法, 使得红队得分恰好比蓝队得分大k。两种方案不同,当且仅当存在某个选手,使得他顺 时针方向的下一个选手在两个方案中不同。 由于答案很大,你只需要输出答案对998, 244, 353 取模后的值。 【输入格式】 从标准输入读入数据。 第一行包含一个整数n,表示选手个数。 第二行包含一个长度为n 的字符串s1s2 · · · sn,表示每个选手所属的队伍。 【输出格式】 输出到标准输出。 输出一行2n + 1 个整数,分别表示k = −n, · · · , 0, · · · , n 的方案数对998, 244, 353 取模后的值。 【样例1 输入】 3 1 BRB 2 【样例1 输出】 0 0 1 1 0 0 0 1 第2 页 共8 页 第三试比赛(match) IOI2025 中国国家集训队集中培训 【样例1 解释】 如图所示,共有两种排列的方法。 第一种排列中,选手1 与2 之间的比赛虽然选手2 获胜,但他属于红队,且在选手 1 顺时针方向,故这场比赛不计入得分。而选手2 和3 之间的比赛蓝方获胜。因此红队 得分为0,蓝队得分为1。 第二种排列中,共进行两场比赛,且均计入得分。红队得分与蓝队得分均为1。 【样例2 输入】 5 1 RBBRR 2 【样例2 输出】 0 0 0 0 8 8 8 0 0 0 0 1 【样例3】 见题目目录下的3.in 与3.ans。 【子任务】 对于所有数据,满足3 ≤n ≤3, 000,s 为由B 和R 构成的字符串。 子任务编号 分值 n 1 ≤17 2 ≤30 10 3 ≤50 4 ≤200 5 45 ≤500 6 15 ≤3, 000 第3 页 共8 页
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3
BRB
0 0 1 1 0 0 0
样例 2
5
RBBRR
0 0 0 0 8 8 8 0 0 0 0