AOJ-ICPC2405 姉妹港

1000なだけあって非常に悩んだけど、面白かった。
































すべての道は交差しないというのが非常に強い制約。
まずは円環はNGなので切って伸ばして列にする。
これのおかげで区間DPとして考えられる。
また、n % 2 == 1の場合は答え1になる事と(r-l) % 2 == 0となる橋は全部無かった事にしていいことが分かる。これを無視すると一気にコーディングが楽になる。
f([l, r]) := 区間[l, r]の橋の渡し方の通りとすればいい
なのでこれで状態数O(N^2)の区間DPになる
ここで、f([l, r])を求める方法について考える。これは、橋が交差しないという制約を利用すると高速に求められる。
まず(r-l) % 2 == 0については0通り、[l, l+1]については1通りでよい。
lから正方向に生えている橋の中で長さr-lより小さい最大の橋を[l, a]とする。もちろんこのときa<r。
[l, r]に橋が生えている場合
f([l, r]) = f([l-1, r+1]) + f([l, a]) * f([a+1, r]) + f([l, a-1]) * f([a, r])
= f([l-1, r+1]) + f([l, a]) * f([a+1, r]) (なぜなら、(a-l) % 2 == 1ゆえ (a-1 - l) % 2 == 0、よってf([l, a-1]) == 0)
[l, r]に橋が生えていない場合
f([l, r]) = f([l, a]) * f([a+1, r])
となる。
これは、l以上aよりも小さいところ->aより大きいところへと生える橋が存在しないことから出せる。
よって、状態数O(N^2)、遷移O(1)のDPになる。
まだ間に合わないので高速化する必要がある。
すべての[l, r]について考えようとするとO(N^2)の力で問答無用で終わる。
ここで、橋を短い順にソートして、順番に橋[l, r]についてf([l, r])を求めていけば良い。
f([l, r])を求めるときにf([l-1, r+1]), f([l, a]), f([a+1, r])が必要だが、もちろんf([l, a])以外は以前に計算しているとは限らない。
なので、常にO(1)でf([l, r])が求められるとは限らない。
しかし、全体ではO(N+Q)に収まるハズ
追記:どこをメモ化するかは気をつけないとO(N^2)です。
イメージとしては[l, r]を計算して、[l, r]を値f([l, r])で包んで、次の[l, r]を計算して…みたいな事を繰り返す感じになるけど、それぞれの橋の区間は一回しか使われない([l,r]の計算に使われたら必ずその区間は[l, r]に覆われる)感じ。

計算量はO(N+QlogQ)かなぁ?ソートをバケツソートにすればO(N+Q)にはなると思う

#include <cstdio>
#include <algorithm>
#include <vector>
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, P> T;
 
const int MN = 50500; 
const int MD = 1000003;
 
int n, m;
P g[MN];
int calc(int l, int r) {
    ll res = 1;
    while (l < r) {
        res *= g[l].second; res %= MD;
        l = g[l].first;
    }
    return res;
}
T e[MN];
int solve() {
    if (n % 2) return 0;
    for (int i = 0; i < n-1; i++) {
        g[i] = P(i+2, 1);
    }
    e[0] = T(n-1, P(0, n));
    int ec = 1;
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        if (a > b) swap(a, b); a--;
        if ((b-a) % 2) continue;
        e[ec] = T(b-a, P(a, b));
        ec++;
    }
    sort(e, e+ec);
    for (int i = 0; i < ec; i++) {
        int a, b;
        tie(a, b) = e[i].second;
        g[a+1] = P(b-1, calc(a+1, b-1));
        g[a] = P(b, (calc(a, b) + g[a+1].second) % MD);
    }
    return g[0].second;
}
 
int main() {
    while (true) {
        scanf("%d %d", &n, &m);
        if (!n) break;
        printf("%d\n", solve());
    }
}