ACPC2017Day1 F Steps - pekempey's blog

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2017Day1&pid=F

dyck 列（正しい括弧列）の数え上げ問題に、深さ上限を与えた問題。dyck 列の総数はカタラン数として知られる。解法の本質はカタラン数の二項係数表現の導出と同じで、エラーが起きた地点から移動方向を反転させるとよい。カタラン数については分かりやすいサイトが見つからなかったため参考リンクは用意していないが、『数学ガール』の 1 巻に書いてあった説明が分かりやすかった覚えがある（読んだの高 1 くらいなので、具体的に何が書かれてたか覚えてないけど）。定番ネタなので探せばいくらでもあるだろう。

たとえば左のような移動経路は、右の移動経路に対応させる。E (エラー地点）から移動方向を反転させている。

        *                 
 *     * G       *        
S-*---*---  <=> S-*-*------     
   E *             E *    
    *                 *   
                       * G'
                        *

S→Gへの経路のうち、下側エラーが起きるパターン数は、S から G' への移動経路数と一致することが言える。ここまではカタラン数の計算方法として有名だろう。

今回は下側だけでなく上側も制約がつく。上側エラーも同様に計算できるが、下側と上側で二重カウントしてしまう。そのため包除原理的に重複を除去していく。

下側エラー→上側エラーとなるパターン数と上側エラー→下側エラーとなるパターン数もまた、先程と同様のテクニックにより計算できる（二回反転させる）。下側エラー→上側エラー→下側エラーというのも同様に計算できる（三階反転させる）。これらが計算できれば、包除原理的に解ける。下→上→下→上→…というのを永遠に求め続ける必要はなく、m の制約からして有限個である（m/n個程度であり、これは計算量に影響を与える）

計算量はわかりづらいが、O(n+m) になる。競技中には計算量解析が雑で、n≤500 のとき別の解法を取るような O( (n+m) sqrt(n) ) の解法を設計していたが、その必要はなかった。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

constexpr int mod = 1e9 + 7;

struct modint {
  int n;
  modint(int n = 0) : n(n) {}
};

modint operator+(modint a, modint b) { return modint((a.n += b.n) >= mod ? a.n - mod : a.n); }
modint operator-(modint a, modint b) { return modint((a.n -= b.n) < 0 ? a.n + mod : a.n); }
modint operator*(modint a, modint b) { return modint(1LL * a.n * b.n % mod); }
modint &operator+=(modint &a, modint b) { return a = a + b; }
modint &operator-=(modint &a, modint b) { return a = a - b; }
modint &operator*=(modint &a, modint b) { return a = a * b; }

modint fact[505050];
modint ifact[505050];
modint inv[505050];

modint C(int n, int r) {
  if (n < 0 || r < 0 || n < r) return 0;
  return fact[n] * ifact[r] * ifact[n - r];
}

modint g(int w, int y) {
  y = abs(y);
  if (w < y) return 0;
  if ((w - y) % 2 != 0) return 0;
  return C(w, (w - y) / 2);
}

int mirror(int y, int u) {
  return -(y - u) + u;
}

modint f(int w, int h, int y) {
  modint ret;
  ret += g(w, y);
  int y1 = y;
  int y2 = y;
  int d1 = -1;
  int d2 = h + 1;
  for (int ii = 0; min(-d1, d2) <= w; ii++) {
    y1 = mirror(y1, d1);
    y2 = mirror(y2, d2);
    if (ii & 1) {
      ret += g(w, y1);
      ret += g(w, y2);
    } else {
      ret -= g(w, y1);
      ret -= g(w, y2);
    }
    d1 -= h + 2;
    d2 += h + 2;
  }
  return ret;
}

int main() {
  fact[0] = 1;
  ifact[0] = 1;
  inv[1] = 1;
  for (int i = 2; i < 505050; i++) {
    inv[i] = inv[mod % i] * (mod - mod / i);
  }
  for (int i = 1; i < 505050; i++) {
    fact[i] = i * fact[i - 1];
    ifact[i] = inv[i] * ifact[i - 1];
  }
  int n, m;
  cin >> n >> m;

  modint ans = 0;
  for (int i = 0; i <= n - 1; i++) {
    ans += f(m, n - 1, i);
  }
  for (int i = 0; i <= n - 2; i++) {
    ans -= f(m, n - 2, i);
  }
  cout << ans.n << endl;
}

そういえば通り数って聞き馴染みがない（twitter 上でしか見ない）んだけど、よく使われる言葉なのだろうか？場合の数という表現は見覚えがある。