#P11968. [2023年联测]切割
[2023年联测]切割
切割(cut)
题目描述
给定长度为 的整数序列。一次操作可以删除两个相邻且数值不同的元素,并将两侧剩余部分连接起来。若一个序列能经过若干次这样的操作变为空序列,称它为好序列。
将原序列划分为一个或多个非空连续段,要求每段都是好序列。求不同划分方案数,模 。只统计分段方案,不统计各段的删除顺序。
输入格式
第一行一个整数 。
第二行 个整数 。
输出格式
输出一个整数,表示答案。
数据范围与评测
,,输入均为整数。Hydro 保留当前全部测试点共 100 分、3 秒、512 MiB 的配置。
本题与 AtCoder ARC159 F — Good Division 相同;全局范围及以下四组样例已按官方题面核对。旧题册中的残缺分档表不作为本版评测条件。
样例 1
3
1 1 2 3 4 5
2
可划分为一整段,或划分为 、 两段。
样例 2
1
1 2
1
样例 3
1
1 1
0
样例 4
12
4 2 17 12 18 15 17 4 22 6 9 20 21 16 23 16 13 2 20 15 16 3 7 15
2048