#P18899. [2026多校联测]双轨灯幕

[2026多校联测]双轨灯幕

题目描述

夜市广场上安装了一面双轨灯幕。灯光设计师准备将节目分批播放:每批使用一条亮度递增的轨道和一条亮度递减的轨道,两条轨道可以交错播放,但全部节目的原定顺序不能改变。

共有 nn 个节目,按编号 1,2,…,n1,2,\ldots,n 的顺序播放。第 ii 个节目的亮度为 pip_i,其中 p1,p2,…,pnp_1,p_2,\ldots,p_n 是 11 至 nn 的一个排列。

设计师需要把全部节目按顺序划分成若干个非空的连续批次,每个节目恰好属于一个批次。对每个批次,需要把其中每个节目恰好分配给一条轨道,使分给向上轨的节目按原顺序组成严格递增序列,分给向下轨的节目按原顺序组成严格递减序列。允许某条轨道在一批中不播放节目;空序列和只含一个节目的序列均满足相应的单调性要求。批次结束后,两条轨道都会复位,下一批的亮度不受上一批影响。

若一个批次的第一个节目编号为 ii,本批需要支付 cic_i 枚月币的启动费用,与本批包含多少个节目无关。全部批次费用相加,就是总费用。

请求出最低总费用,以及达到最低总费用的合法分批方式数量。仅对方式数量取模,模数为 998244353998244353。

两种方式不同,当且仅当它们的批次分界位置不同。同一批次即使有多种轨道分配方式,也不重复计数。

输入格式

第一行一个整数 nn。

第二行 nn 个整数 p1,p2,…,pnp_1,p_2,\ldots,p_n。

第三行 nn 个整数 c1,c2,…,cnc_1,c_2,\ldots,c_n。

输出格式

输出一行两个整数:最低总费用,以及最优分批方式数量对 998244353998244353 取模的结果。最低总费用本身不取模。

样例 1 输入

4
2 1 4 3
5 2 1 4

样例 1 输出

6 1

样例 1 解释

四个节目不能同时放在一个批次中:亮度 2,12,1 不能都上向上轨,亮度 4,34,3 也不能都上向上轨,因此向下轨至少要取前一对和后一对中的各一个;而前一对的任意亮度都小于后一对,无法严格递减。

在第 22 个节目后分批,得到 [2,1][2,1] 和 [4,3][4,3],费用为 c1+c3=6c_1+c_3=6,两批都可以全部放在向下轨。其他分界方式没有同样低的费用,故答案为 6 16\ 1。

样例 2 输入

5
1 2 3 4 5
7 0 2 0 0

样例 2 输出

7 8

样例 2 解释

整个排列严格递增,任意批次都合法。第一个批次必须支付 77 枚月币;第 2,4,52,4,5 个节目均可以免费另开一批,每个位置可选可不选,共有 23=82^3=8 种最低费用方案。

样例 3

见下发材料中的 ribbon/3.in 和 ribbon/3.ans。这是接近完整规模的附件,不在题面中展开。

子任务

对于所有测试数据,保证:1≤n≤2000001\le n\le200000,pp 是 11 至 nn 的排列,0≤ci≤1090\le c_i\le10^9。

各子任务独立整组计分,通过该组全部测试点才能得到该组分数;各组无依赖关系。

子任务 分值 额外约束
1 20 n≤10n\le10
2 n≤800n\le800
3 pp 严格递增或严格递减
4 40 无额外约束