#P11968. [2023年联测]切割

    ID: 11118 传统题 3000ms 512MiB 尝试: 3 已通过: 1 难度: 8 上传者: 标签>动态规划数据结构贪心CF2400前缀和数学二分

[2023年联测]切割

切割(cut)

题目描述

给定长度为 2n2n 的整数序列。一次操作可以删除两个相邻且数值不同的元素,并将两侧剩余部分连接起来。若一个序列能经过若干次这样的操作变为空序列,称它为好序列。

将原序列划分为一个或多个非空连续段,要求每段都是好序列。求不同划分方案数,模 998244353998244353。只统计分段方案,不统计各段的删除顺序。

输入格式

第一行一个整数 nn。

第二行 2n2n 个整数 a1,ldots,a2na_1,ldots,a_{2n}。

输出格式

输出一个整数,表示答案。

数据范围与评测

1lenle5imes1051le nle5 imes10^5,1leaile2n1le a_ile2n,输入均为整数。Hydro 保留当前全部测试点共 100 分、3 秒、512 MiB 的配置。

本题与 AtCoder ARC159 F — Good Division 相同;全局范围及以下四组样例已按官方题面核对。旧题册中的残缺分档表不作为本版评测条件。

样例 1

3
1 1 2 3 4 5
2

可划分为一整段,或划分为 (1,1,2,3)(1,1,2,3)、(4,5)(4,5) 两段。

样例 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

旧题册原页