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()); } }