【题解】ARC100D Colorful Sequences | 20211215 模拟赛 序列【DP】

本文主要是介绍【题解】ARC100D Colorful Sequences | 20211215 模拟赛 序列【DP】，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目链接

题目链接

题意

定义一个序列是彩色的当且仅当其有一个子段为 \(k\) 的排列。问所有长度为 \(n\)，值域为 \(k\) 的彩色序列中序列 \(a\) 作为子串出现了多少次。\(n\leq 25000,k\leq 400\)

题解

先特判 \(a\) 是彩色的情况。接着考虑 \(a\) 互不相同的情况，设 \(f_{i,j}\) 为长为 \(i\) 的序列最近 \(j\) 个数不同的方案数，相应记录 \(g\) 代表互不相同的长为 \(|a|\) 的段出现的次数。所有等长度的互不相同的段出现次数一样，所以答案要除掉一个下降幂。若 \(a\) 有相同，分 \(a\) 往左往右扩展来 DP。

这篇关于【题解】ARC100D Colorful Sequences | 20211215 模拟赛 序列【DP】的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！