#P18675. Classical FFT Problem
Classical FFT Problem
Classical FFT Problem
题目描述
考虑一个有 行、 列的方格网格。Arbok 剪掉了其中的一部分,使得从上往下第 行只剩下最左边的 个格子。满足 ,因此剩余部分构成一个杨图。Arbok 想在剩余的一些格子中放置国际象棋的车。
一个车占据一个格子,可以沿水平方向或竖直方向,经过任意数量未被占据的格子移动。若一个格子本身有车,或者某个车能通过一次移动到达该格子,就称这个格子被覆盖。
求覆盖所有剩余格子所需放置的最少车数 ,以及恰好放置 个车并覆盖全部剩余格子的摆法数 ,其中 对 取模。每个车只能放在剩余格子中;不同的占用格子集合算不同摆法。不要求车彼此不能攻击,同一行或同一列可以放多个车。
输入格式
第一行包含整数 ()。
第二行包含 个整数 ,满足 ,表示各行剩余的宽度。输入没有测试用例数 。
输出格式
输出两个整数 ,分别为覆盖所有剩余格子所需的最少车数,以及达到该最少车数的摆法数对 取模的结果。
样例输入 1
3
1 2 3
样例输出 1
2 6
样例说明
一个车不足以覆盖所有格子,但两个车就足够。共有如下六种摆法,R 表示车,* 表示未放车的格子:

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