SRM542 Div1 Easy

250

まず、Tを決める。
高さ H 幅 W の四角形を考える。端から端まで使うような経路では T = 2 * (H + W)
中継地点の座標の選び方は (H - 1) * (W - 1) 通り。
その四角形の中から3点を選ぶパターンは、X座標Y座標を３つずつ選んで、
それを組み合わせてできる座標の数。つまり、3!
ex.) X = {0, a, W}, Y = {0, b, H} から作れる座標を組みは3!通り。

それを掛けて足しあわせていけばいい。

分かりやすく説明できないー。

class PatrolRoute {
public:
  int countRoutes(int X, int Y, int minT, int maxT)
  {
    const lli mod = 1000000007;

    lli ret = 0;
    for (int x = 2; x < (int)X; ++x) {
      for (int y = 2; y < (int)Y; ++y) {
        int T = 2 * (x + y);
        if (minT <= T && T <= maxT) ; else continue;
        lli a = X - x;
        lli b = Y - y;
        ret += a * b * (x - 1) * (y - 1) * 6LL;
        ret %= mod;
      }
    }

    return ret;
  }
};