某島

… : "…アッカリ~ン . .. . " .. .
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