『STA - R9』咏叹调调律 - 题目详情

ID: 13522

远端评测题

1000ms

512MiB

难度: 7

上传者:

标签>

动态规划 DP

贪心

O2优化

题目描述

一段旋律是一个仅含 $\tt ABC$ 的字符串 $S$ 。一段旋律被称作咏叹调当且仅当可以通过每次删除一个 $\tt AB$ 子序列、 $\tt CA$ 子序列、 $\tt AAA$ 子序列或 $\tt CCB$ 子序列来得到空串。

对于非负整数 $p,q,r$ ，一段含 $a$ 个 $\tt A$ 、 $b$ 个 $\tt B$ 、 $c$ 个 $\tt C$ 的旋律的音韵被定义为 $p^aq^br^c$ （其中 $0^0=1$ ）。

给定正整数 $n,p,q,r$ ，对于每个 $1\le k\le n$ ，问长度为 $k$ 的咏叹调的音韵之和。答案可能很大，对 $998244353$ 取模。

一行四个非负整数 $n,p,q,r$ 。

一行 $n$ 个非负整数，表示对于每个 $1\le k\le n$ ，长度为 $k$ 的咏叹调的音韵之和。对 $998244353$ 取模。

4 1 1 1

0 2 2 9

样例解释

长度为 4 的咏叹调：AABB, ABAB, ABCA, ACAB, ACBA, CAAB, CABA, CACA, CCAA。

数据范围

本题各数据点分值等分。令 $M=998244353$ 是模数。

测试点编号	$n$	$p$	$q$	$r$
$1$	$\le 10$	$\in[0,M)$	$\in[0,M)$
$2$	$\le200$	$\in[0,M)$	$=0$
$3\sim4$		$=0$	$\in[0,M)$	$\in[0,M)$
$5\sim6$		$\in[0,M)$	$=0$	$\in[0,M)$
$7\sim8$			$\in[0,M)$	$=0$
$9\sim11$	$\le30$			$\in[0,M)$
$12\sim14$	$\le50$
$15\sim19$	$\le200$
$20$	$\le500$

对于全部数据， $1\le n\le 500$ ， $0\le p,q,r<M$ 。