コード
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <fstream>
#include <iostream>
#include <set>
#include <sstream>
#include <typeinfo>
#include <vector>
using namespace std;
typedef long long ll;
class WolfPackDivTwo {
int dist(int x1, int y1, int x2, int y2) {
return abs(x1 - x2) + abs(y1 - y2);
}
const int MOD = 1000000007;
public:
int calc(vector<int> x, vector<int> y, int m) {
int N = x.size();
const int S = 300, P = 100;
vector<vector<ll>> dp(vector<vector<ll>>(S, vector<ll>(S, 0)));
dp[P][P] = 1;
for (int r = 0; r < m; ++r) {
vector<vector<ll>> next(vector<vector<ll>>(S, vector<ll>(S, 0)));
for (int i = 0; i < S; ++i) {
for (int j = 0; j < S; ++j) {
if (i > 0) next[i - 1][j] = (next[i - 1][j] + dp[i][j]) % MOD;
if (i < S - 1) next[i + 1][j] = (next[i + 1][j] + dp[i][j]) % MOD;
if (j > 0) next[i][j - 1] = (next[i][j - 1] + dp[i][j]) % MOD;
if (j < S - 1) next[i][j + 1] = (next[i][j + 1] + dp[i][j]) % MOD;
}
}
dp.swap(next);
}
ll ans = 0;
for (int px = -50; px <= 150; ++px) {
for (int py = -50; py <= 150; ++py) {
ll tmp = 1;
for (int i = 0; i < N; ++i) {
int d = dist(x[i], y[i], px, py);
if (d > m || (d - m) % 2 != 0) tmp = 0;
tmp = (tmp * dp[px - x[i] + P][py - y[i] + P]) % MOD;
}
ans = (ans + tmp) % MOD;
}
}
return (int)ans;
}
};