题目中的权值 $g(n)$ 是对于极长连续段的，我们先将其改为所有连续段，即 $f(n)=g(n)-2g(n-1)+g(n-2)$。
枚举连续段，那么对于未出现在段中的数，每种数的方案数是 $2^{cnt(x)}-1$，否则每个数的方案数是 $2$。注意到我们只需要知道段中出现了哪些数，对于每个左端点，这只有 $m$ 种情况，预处理一些前缀和就能 $O(1)$ 计算。
总时间复杂度 $O(nm)$。
QOJ.ac
QOJ
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
Discussion #163 for Problem #7219. The Mighty Spell
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-12 23:45:11
Last updated: 2025-12-12 23:45:17
题解
Comments
No comments yet.