某岛

… : "…アッカリ~ン . .. . " .. .
March 28, 2013

Dhaka 2012 Regional Contest

Problem A. Divisibility

Brief description:

… 给定一个 n-维 Grid,每个格点的数值,是其 “下方” 所有格点的数值和。源点的数值为 0。
。。求一个子矩形内,不能被 P 整除的格点总数。
(n < 8, 1 < P < 20 ...)

Analysis:

… 把坐标的每一维分量看成一个 P 进制整数。。。。那么对应格点的数值不被 P 整除就是数位不等于 0。。
。。。于是 subtask 可以用数位 DP。。
。。。对每一个维度。枚举是否低于边框。。。外层暴力容斥原理。。
。。需要注意的是这里 “限制” 因为不只一个数。。需要状态压缩。。~。。。

状态 f(c, r, s, b)表示:
。。。当前考察第 c 个数位,第 r 维分量。。模 P 的和为 s。。限制状态集合为 b 时的方案数。。

http://acm.hust.edu.cn/vjudge/contest/viewSource.action?id=1035844

External link:

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=18127#problem/A