#P18675. Classical FFT Problem

    ID: 18011 传统题 10000ms 512MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-容斥原理乘法原理排列数计算分治乘积多点求值乘积树多项式除法多项式求逆多项式牛顿迭代NTT阶乘逆元预处理

Classical FFT Problem

Classical FFT Problem

题目描述

考虑一个有 nn 行、nn 列的方格网格。Arbok 剪掉了其中的一部分,使得从上往下第 ii 行只剩下最左边的 aia_i 个格子。满足 a1≤a2≤⋯≤ana_1\le a_2\le\cdots\le a_n,因此剩余部分构成一个杨图。Arbok 想在剩余的一些格子中放置国际象棋的车。

一个车占据一个格子,可以沿水平方向或竖直方向,经过任意数量未被占据的格子移动。若一个格子本身有车,或者某个车能通过一次移动到达该格子,就称这个格子被覆盖。

求覆盖所有剩余格子所需放置的最少车数 rr,以及恰好放置 rr 个车并覆盖全部剩余格子的摆法数 ww,其中 ww 对 998244353998244353 取模。每个车只能放在剩余格子中;不同的占用格子集合算不同摆法。不要求车彼此不能攻击,同一行或同一列可以放多个车。

输入格式

第一行包含整数 nn(1≤n<2171\le n<2^{17})。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,满足 1≤a1≤a2≤⋯≤an≤n1\le a_1\le a_2\le\cdots\le a_n\le n,表示各行剩余的宽度。输入没有测试用例数 TT。

输出格式

输出两个整数 r,wr,w,分别为覆盖所有剩余格子所需的最少车数,以及达到该最少车数的摆法数对 998244353998244353 取模的结果。

样例输入 1

3
1 2 3

样例输出 1

2 6

样例说明

一个车不足以覆盖所有格子,但两个车就足够。共有如下六种摆法,R 表示车,* 表示未放车的格子:

原题PDF中的六种摆法

上图直接截取自官方原题 PDF 第5页,保留原始六种摆法及排列,未重绘。在Hydro中将 sample_placements.png 作为题面附件引用。