UVA 12633 Super Rooks on Chessboard

正文索引 [隐藏]

传送门:http://vjudge.net/problem/UVA-12633

题目翻译

超级车可以攻击行、列、主对角线 3 个方向。R∗C的棋盘上有N个超级车,问不能被攻击的格子总数。(R,C,N≤50000)

题解

首先行和列的格子情况我们很容易处理。
然后我们观察主对角线,在一条主对角线上的格子的特征很明显 i – j 为一个定值。
用R[x]表示某一行不被行攻击,C[x]表示某一列是否不被列攻击。那么一条主对角线上没有被行列攻击的格子数量为D[k] = ∑ ∑ ( R[i] * C[j] * [i – j == k])
如此可以使用FFT处理。

代码