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
