#P3587. [POI 2015] POD

    ID: 4424 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>2015单调队列POI(波兰)哈希 hashing

[POI 2015] POD

题目描述

长度为 nn 的一串项链,每颗珠子是 kk 种颜色之一。第 ii 颗与第 i1,i+1i-1,i+1 颗珠子相邻,第 nn 颗与第 11 颗也相邻。

切两刀,把项链断成两条链。要求每种颜色的珠子只能出现在其中一条链中。

求方案数量(保证至少存在一种),以及切成的两段长度之差绝对值的最小值。

输入格式

第一行 n,kn,k2kn1062\leq k\leq n\leq 10^6)。颜色从 11kk 标号。

接下来 nn 个数,按顺序表示每颗珠子的颜色。(保证 kk 种颜色各出现至少一次)。

输出格式

一行两个整数:方案数量,和长度差的最小值。

9 5
2 5 3 2 2 4 1 1 3
4 3

提示

【样例解释】

四种方法中较短的一条分别是 (5),(4),(1,1),(4,1,1)(5),(4),(1,1),(4,1,1)。相差最小值 63=36-3=3


原题名称:Podział naszyjnika。