Hamako Online Judge #097 ukuku09: 005 - devilswalk
- https://hoj.hamako-ths.ed.jp/onlinejudge/contest/97/problems/5
- https://hoj.hamako-ths.ed.jp/onlinejudge/problems/770
$5$完で$6$位。やったね。
solution
隣接行列を$T$乗する。$O((WH)^3 \log T)$。速めの行列積を書けば通る。
implementation
#include <array>
#include <cmath>
#include <cstdio>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
using ll = long long;
using namespace std;
const int dy[] = { -1, 1, 0, 0 };
const int dx[] = { 0, 0, 1, -1 };
bool is_on_field(int y, int x, int h, int w) { return 0 <= y and y < h and 0 <= x and x < w; }
constexpr int max_h = 16;
constexpr int max_w = 16;
constexpr int mod = 1e9+7;
using type = array<array<int, max_h * max_w>, max_h * max_w>;
type append(type const & a, type const & b) {
type tb;
repeat (i, max_h * max_w) {
repeat (j, max_h * max_w) {
tb[i][j] = b[j][i];
}
}
type c;
repeat (i, max_h * max_w) {
repeat (j, max_h * max_w) {
ll acc = 0;
repeat (k, max_h * max_w) {
acc += a[i][k] *(ll) tb[j][k] % mod;
}
c[i][j] = acc % mod;
}
}
return c;
}
int main() {
int w, h, t; scanf("%d%d%d", &w, &h, &t);
array<array<bool, max_h>, max_w> object = {};
repeat (y, max_h) repeat (x, max_w) {
object[y][x] = not is_on_field(y, x, h, w);
}
int object_count; scanf("%d", &object_count);
repeat (i, object_count) {
int x, y; scanf("%d%d", &x, &y); -- x; -- y;
object[y][x] = true;
}
type e = {};
repeat (y, h) repeat (x, w) {
if (object[y][x]) continue;
repeat (i, 4) {
int ny = y + dy[i];
int nx = x + dx[i];
if (not is_on_field(ny, nx, h, w)) continue;
if (object[ny][nx]) continue;
e[y * max_w + x][ny * max_w + nx] += 1;
}
}
type result = {};
repeat (y, h) repeat (x, w) {
if (object[y][x]) continue;
result[y * max_w + x][y * max_w + x] = 1;
}
for (int i = 1; i <= t; i <<= 1) {
if (t & i) {
result = append(result, e);
}
e = append(e, e);
}
int query; scanf("%d", &query);
while (query --) {
int sx, sy, gx, gy; scanf("%d%d%d%d", &sx, &sy, &gx, &gy); -- sx; -- sy; -- gx; -- gy;
printf("%d\n", result[sy * max_w + sx][gy * max_w + gx]);
}
return 0;
}