Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2012-05-28

[][] Codeforces Round #120 : E. Counter Attack 01:18 はてなブックマーク -  Codeforces Round #120 : E. Counter Attack - 練習帳

問題文

 問題文

概要

  • 無向グラフが与えられている。
  • このグラフの補グラフを連結成分に分解せよ。
    • グラフG=(V, E)の補グラフG'とは、節がGと同じで、枝は(v, w)∉E(v, w∈V)となるグラフのことである。つまり、もとのグラフの枝の有無を反転させたグラフのこと。
  • 条件:節:n ≦ 5*10**5、枝:m ≦ 10**6

コード

 Practiceでの提出コード(解1):http://codeforces.com/contest/190/submission/1715799

 Practiceでの提出コード(解2):http://codeforces.com/contest/190/submission/1715764

 UnionFindはライブラリから使用:https://github.com/delta2323/algorithm_library

考えた過程

第一歩

一般の場合n**2≫mなので、補グラフはほぼ完全グラフになってしまっています。

nが小さければ、深さ優先探索なりUnion Findなりを使って連結成分分解は簡単にできます。しかし今回はn**2が大きいためにこれらの方法をそのままは使えません。何か飛び道具のようなうまい方法がないかと考えたのですが、結局思いつきませんでした。そこで、ベタに連結成分を計算する方法をうまく工夫して軽くできないかを検討しました。

未決定集合を持つ→失敗

最初に考えたのは、データの持ち方の方での工夫でした:まだどの連結成分に属するかが決まっていない節の集合(未決定集合)を持っておきます。深さ優先探索である節から隣接する節に移動する時には、その節が未決定集合に入っているかを調べ、すでに未決定集合から除かれている場合には移動しない事で枝狩りします。計算量的には問題ないと思うのですが、書き方が下手でRuntime Errorになってしまいました(後述のNG解の1つ目がそれです)。setをiteratorで回しながらstd::set::erase(iteraotr)でその要素を削除しているのでiteratorが無効になっています。

クラスタの数を少なくして連結成分分解

節の数がn個ある完全グラフを深さ優先探索すると、枝の持ち方を工夫しないと計算にO(n**2)だけかかってしまい、これがこの問題のネックになっています。そこで次の方法として、節を予めまとめあげて節の数を減らしてから、深さ優先探索ができないかを考えました。具体的には、二段階に分かれます。第一段階では、節達のうち距離1でつながっているもの達をある程度つなげることでクラスタにまとめ上げ、第二段階でクラスタに対して(ナイーブな)連結成分分解を行います。どちらの段階も最悪O(n**2)だけかかるのですが、今回の(補)グラフが密である事を用いると第一段階では相当な枝狩りが期待でき、第二段階ではクラスタ数が少なくなることが期待できます。実際うまく制限時間に収まりました(解1)。

無効なiteratorを用いないようにしながらtraverseする

Editorialを読んでみると、どうやら節同士をまとめてクラスタにするような事をしなくても、NG解1で考えていた、未決定集合を保持しながら幅優先探索で解答が得られるようです。ただ、setから単純に値を削除してしまうとiteratorが無効になってしまうので、実装の方法を少し工夫が必要でした。その工夫方法がこちらなどで紹介されていました。この方法を用いたのが(解2)です。

NG集

2012-05-20

[][] Codeforces Round #119 : C. Weak Memory 18:56 はてなブックマーク -  Codeforces Round #119 : C. Weak Memory - 練習帳

問題文

 問題文

概要

  • 無向連結グラフが与えられている(節:n個、枝:m本)
  • グラフのうちk個の節に印がついている
  • スタート地点とゴール地点が与えられている
  • 次の条件を満たす正数qのうち、最小の値を求めよ。条件を満たすqがない場合には-1と答えよ。
    • 条件:「スタートからゴール地点への経路のうち、次の条件を満たすものが存在する。スタート地点からqステップ以内に印つきの節がある、さらにその印つきの節からqステップ以内に印つきの節がある...これを繰り返してゴール地点までたどり着ける。」
  • 制限
    • n ≦ 10**5, m ≦ 2*10**5, k ≦ n, 実行時間2秒以内

コード

 Practiceでの提出コード:Submission #1683870 - Codeforces

 UnionFindはライブラリから使用:no title

考えた過程

方針1:印つき節のみのグラフを作れるか?

 もし印つき節だけ取り出し、節間の距離を元のグラフでの最短距離とするグラフを作れれば、その上でダイクストラに近いことを行えば、与えられた課題を解くことができそうです(各節の上で、通常の「その節までの最短距離」の代わりに「その節に到達するまでにたどった枝のコストの最大値」を覚えます)。すると問題はそのような最短距離を結んだグラフが作成可能に帰着できます。でもそれは難しそう。一番嬉しいのは2つの印つき節間の距離がすべて求まる事ですが、それにはワーシャルフロイドを行う必要がありますが、印つき節の最大数は10**5なので、計算量的に無理で、仮にできたとしてもメモリが足らなさそうです。印つき節間の距離を全部は計算しないで計算が間に合うようにするということも考えられるけれど、必要不必要の判断をどのように行うかがパッとは思いつかないです。とりあえずこの方針ではこの先に思いつきませんでした。

方針2:qについて2分探索

 次に考えたアイデアはqの値について2分探索が出来る事です。つまり、ある値qでスタートからゴールまでたどり着くことが可能なら、qより大きい値でもたどり着くことは可能なので2分探索が使えます。qが3なり4なりある特定の定数になってしまえば、今いる印つきの節からqステップ以内にある印つきの点を深さ優先的に探索することで、ゴールに辿り着けるか調べられます。つまり、「ある印つき節移動する→その点を始点とするダイクストラを実行し、qステップ以内の印つき節を見つける→それらを順番に訪問する→・・・」とすれば良いです。でもダイクストラは無駄な計算をものすごくしているような気がする。ダイクストラの計算量がO(m+nlogn), 印つき節の深さ優先探索でO(k)なので、合計の計算量は大雑把にO(k(m+nlogn))。やっぱり計算量的に難しそう。

 ただ、qについて2分探索の方はそれなりに良さそうな気がしていて、印つきの2つの節について「枝が貼られている」⇔「qステップで移動可能」でグラフを作れば、求める条件は新しく作ったグラフの上でスタート地点とゴール地点が連結であるというところまで問題を簡単にできます。連結かどうかを調べるのは、深さ優先探索でもUnionFindでもできるので、この部分はあまり気にする必要がなさそうです。ただ、この場合も方針1の時と同じように、すべての印つき節のペアについてqステップで移動可能かを考えていたら時間は足らなくなってしまう。

解答

 ここまでで良くわからなくなりギブアップ。他の方の回答を見ていたのですが、以下の方針がしっくり来ました。以下のSubmissionを参考にさせていただきました。

「qステップで移動可能か」という条件のチェックがナイーブな方法では全く時間が足らないですが、この部分を工夫して計算量を減らすのがポイントだと思います。方針は次のとおりです。各節(印つきとはかぎらない)で「最も近い印つき節」と「その印つき節までの距離」の2つを覚えておきます。節vに対するこれらの値をv.n(neighbour), v.d(distance)と置く事にすると、印つき節をつなげるための規則は枝(v, w)に対して「v.d+1+w.d <= qならばv.nとw.nをつなげる」となります。キューに(v.n, v.d)を入れて、順番にこの規則を適用します。(v.n, v.d)の情報に更新があったら、その更新情報をキューに追加します。

最初に挙げた自分の提出コードに対して、次のテストケースを与えた場合を考えます。このテストケースはT字型をしたグラフでTの先端3箇所にvolunteerがいます。T字の上棒の左端が1, 右端が42, T字の下端が27番の節です。連結部分は26番で1-26間の距離は25, 26-27間の距離は15, 26-42間の距離は30です。答えとなるq=45のケースでは、T字を遠回りしなければゴールにつけません。気になるのはq=55の時で。この場合スタートからゴールまで直接移動できるのですが、自分の提出アルゴリズムでは、やはりT字を遠回りする道を選択しています。つまり、印つき節に対し「枝が貼られている」⇔「qステップで移動可能」となっているグラフよりも少ない枝を張っている事で計算量が抑えられているのだと思います。各節に対して覚えておくのは最も近い印つき節だけで覚える事でそれを達成しています。

不安になるのは、節のつなぎ漏れがないかということです。実を言うと自分でも何故これで正しくできるかをきちんとは理解できていないですのですが、今回の提出コードではそれで十分だったようです。

2012-05-14

[][] Codeforces Round #118 : D. Visit of the Great 23:57 はてなブックマーク -  Codeforces Round #118 : D. Visit of the Great - 練習帳

問題文

 問題文

概要

  • クエリとして整数の四つ組(k, l, r, p)が与えられている(pは素数)
  • 各クエリに対して、LCM(k**(2**l)+1, k**(2**(l+1))+1, ..., k**(2**r)+1)をpで割ったあまりを答えよ
  • 制限
    • クエリの数は10**5個以下
    • 1 ≦ k ≦ 10**6, 0 ≦ l ≦ r ≦ 10**18; 2 ≦ p ≦ 10**9

コード

 Practiceでの提出コード:Submission #1671135 - Codeforces

考えた過程

1クエリの重さはどのくらい?

クエリの数が多いので、クエリに依存しない前処理を行った後にクエリをまとめて処理するか、ひとつひとつのクエリ処理がものすごく軽いかのどちらかと考えられます。k, l, r, pの取りうる値の範囲が広く、登場するk**(2**e)+1の値がすべて違うということも起こりえるので、あるk, l, r, pの4つ組での答えから別の4つ組みについて情報が得られないといけません。でも、例えばk=2の場合での計算をk=3の場合に利用できるとは考えづらいです。今回は後者の1つ1つの処理が軽いのではないかと予想して話を進めていこうと思います。駄目だったら前処理を行うことを考えてみます。

素因数分解?

最小公倍数を求めるならば、とりあえず素因数分解をしてみようと思いつきました。しかしk**(2**x)+1という形は非常に素因数分解と相性が悪い気がします。k, xの値からk**(2**x)+1の素因数分解がどのような形をしているのかはほとんど予想できないです。しかも今回の場合得られた最小公倍数をpで割らないとなりません。aの素因数分解をaをpで割った余りから求めるのは難しそうです。素因数分解する方針は難しそうです。

分からない → 実験

全然方針が立たないので、具体例を考えるか問題を簡単にしてヒントを見つけようと思います。簡単にする方法としてすぐに思いつくのは、例えば次のものがあります。

  • x=k**(2**l)と置いてみる
  • r=l+1と置いてみる。つまり最小公倍数を2つの数で取ってみる
  • k=2とか3で決め打ちしてみる

x=k**(2**l)と置いてみると、最小公倍数を取る値は、x+1, x**2+1, x**4+1, x**8+1...となります。尽く偶数乗なのが嬉しくないです。これがx**3+1とかになっていればx**3+1=(x+1)(x**2-x+1)とかになって、だから何かはわからないですが、なんとなく手が進むような気がしましたが...

別の簡単化も考えます。出てくる数が2つの場合で考えます。2つで考えると何が嬉しいかというと、最小公倍数がかなり具体的な式で求まります。つまり、LCM(x, y) = x*y/GCD(x, y)です。求めたいのは、先ほどのx=k**(2**l)を用いると、LCM(x+1, x**2+1)です。すると、GCM(x+1, x**2+1)はxの偶奇に応じて1 or 2となります(自分はようやくこのあたりで手がかりを見つけたような感じがしました)。最小公倍数が(x+1)(x**2+1) or (x+1)(x**2+1)/2と答えを具体的に書けました。しかも今回の場合、さらに嬉しいのが、LCMが四則演算で書けているので剰余を取る操作とも相性が良いです。

2つの方法を3つに応用できないか?

2つの場合でうまく行きそうなので、3つ以上の場合に話を拡張できないかと考えます。LCM(a, b, c) = LCM(LCM(a, b), c)なので、再帰的に2つの場合の議論が適用できそうです。しかし、そのままやってみると、

LCM(LCM(x+1, x**2+1), x**4+1) = LCM( (x+1)*(x**2+1))/[2] , x**4+1) = LCM( (x**3+x**2+x+1)/[2] , x**4+1)

となります。ここで、[2]はxの偶奇によってあったりなかったりすることを意味します。よくわからない形になりますが、試しに、x**4+1を(x**3+x**2+x+1)で割り算して、同じように最小公倍数を求められないかを考えてみます。すると(x**3+x**2+x+1)(x-1)+2と先ほどと同じように余りが2になることがわかります。先程と同様xの偶奇に応じて最大公約数が1 or 2です。

今は割り算をしましたが、(x**3+x**2+x+1)の方を見ても、x**k-1という形の式の因数分解でx**4-1=(x**3+x**2+x+1)(x-1)というのがあるので、そちらからもこの計算はできます。

結局3個の場合、最小公倍数は

  • xが奇数の場合:(x+1)(x**2+1)(x**4+1)/2/2
  • xが偶数の場合:(x+1)(x**2+1)(x**4+1)

とわかりました。

具体的な値で確かめてみる

ちょっと自信がないので、具体的に数字を当てはめて計算してみます。今回は小さな値でも計算途中の値が大きくなってしまいそうなので、小さめの数にしておきます(コーナーケースにぶつかってしまう危険性はありますが...)。 xはそもそもk**(2**l)という形をしていたことも気にすると、

  • k=2, l=1(→x=4):LCM(4+1, 16+1, 256+1) = LCM(5, 17, 257)=5*17*257
  • k=3, l=1(→x=9):LCM(9+1, 81+1, 6561+1) = LCM(10, 82, 6562)=LCM(5, 41, 3281)/2=10*82*6562/2/2

となりよさそうな感じがします。今から思うと、先ほど挙げた、k=2, 3で予想を立てたほうが結論に早く到達できたかもしれないです。

一般の場合でも同じことは適用できるか?

さて、3つでもできました。嬉しいのは3つの場合を2つの場合と類似した方法で解けた事で、この方法を再帰的に繰り返すことで、一般の個数の場合に問題を解けそうです。細かい計算は省略しますが、これは一般の場合でも正しいことがわかって、

  • xが奇数の場合:(x+1)(x**2+1)・・・(x**(2**(r-l+1))+1)/2**(r-l)
  • xが偶数の場合:(x+1)(x**2+1)・・・(x**(2**(r-l+1))+1)

となります。分子が複雑な形をしていますが、これは「LCMを計算すべき数をすべて掛け算する」ということを無理やり数式で表現しようとしているだけです。

(x+1)(x**2+1)(x**4+1)・・・の計算を簡単化する

答えが明示的に式で与えられたのは嬉しいのですが、まだ駄目です。今の制限では、r, lが10**18以下なので、この値をfor文などを用いてこのままの形で計算することは出来ません。何らかの方法で計算を省略しないとなりません。

ぱっと思いついたのは、フェルマーの小定理x**p = x mod pを用いて、「実はこれらの値はかなり重複をしている」とか、「実は値がループしている」とかのからくりが働いて計算が簡単になるとかが起こらないかということです。もう一つのアプローチは同じように値が3つの場合などで試してみてわかりました。

(x+1)(x**2+1)(x**4+1) = (x**3+x**2+x**1+1)(x**4+1) = x**7+x**6+・・・+x+1 = x**8-1/x-1

となります。つまり、この値は等比級数の和の公式で書けます。この式ならば、l, rなどが大きくても時間をかけずに計算できるので、計算できそうです。後者の方を使うと、結局、求めるべき値は、

  • xが奇数の場合:(x**(2**(r-l))-1)/(x-1)/2**(r-l)
  • xが偶数の場合:(x**(2**(r-l))-1)/(x-1)
xの偶奇とx mod pを求める。

さて最後に残ったのが、x=k**(2**l)の偶奇の判定と、xの値の計算です。前者は単純で、kの偶奇がそのままxの偶奇になります。後者についてはxの値をそのまま計算はできないので、これをmod pした値を計算します。

これは前述したフェルマーの小定理を用いて計算をできます。つまり、k**p = k (mod p)を1回の操作で肩の指数がp-1だけ減る操作だと思うと、x mod pの値はk**(2**l mod (p-1))を計算すればよさそうです。つまり擬似コードにするとこんな感じです。

   e = modpow(2, l, p-1) // modpow(r, a, q)はr**aをqで割った余り
   x = modpow(k, e, p)

自分も一度これで書いて提出したのですが、Wrong answerになりました。間違いケースを見てみると、k=pというケースでした。つまり、上のコードは実際にはフェルマーの小定理をk**(p-1) = 1 (mod p)の形で用いていて、この形のフェルマーの小定理はkとpが互いにその場合しか成立していません。この部分を修正したのが前述の提出コードが得られました。

コーナーケース

実際にコードを書いてみると(そして提出して何回もWAをもらうと)この議論には様々なコーナーケースがあることに気付かされます。例えば次のようなものがありました。

  • 等比級数の和の公式はる公比が1の場合分けを行う。
  • kとpが等しい場合k**(2**l)とk**(2**l % (p-1))は等しくない。
  • p=2の場合mod pのレベルでxで割る操作をxをp-2乗する操作は等しくない

2012-05-06

[][] ABBYY Cup 2.0 - Hard : B. Greedy Merchants 15:32 はてなブックマーク -  ABBYY Cup 2.0 - Hard : B. Greedy Merchants - 練習帳

問題文

 問題文

概要

  • 無向連結グラフが与えられている。
  • クエリとして、スタート地点とゴール地点のペアが与えられる。
  • 各クエリに対して、「もしその枝がグラフから除かれたら、スタートからゴールまで辿り着けなくなる」という枝の本数を答えよ。
  • 制限
    • グラフの節の数:n ≦ 10**5, グラフの枝の数:m ≦ 10** 5, クエリの数:k ≦ 10**5

コード

 Practiceでの提出コード:Codeforces

 LCA, RMQはライブラリを用いています:no title

考えた過程

第一歩

すぐに思いつくこととして次の二つがあります。

一つは、それぞれの枝を取り除いて、ダイクストラ法 or ワーシャルフロイドを行い、スタートからゴールまでたどり着けるかを検査するという方法では計算量的に間に合わないと言うこと。あるいはもっと一般に、各クエリごとにグラフに対して思い処理を行うような解法は取れないということです。つまり、最初にグラフに対して前処理を行った後に、クエリに対して短時間で答えられるような処理でないといけません。

もうひとつは「その枝を除いてしまったらグラフが非連結になってしまうような枝」を探せば良さそうという事(後で見てみると、このような枝のことを「ブリッジ」と呼ぶ事が多いらしいです)。もしこれがわかるならば、ブリッジとなる枝が、それぞれのクエリで何回数えられるかに問題が帰着できます。これは一つ目に思いついたことと相性がよさそうです。

ブリッジを見つければ良さそう

ブリッジを見つけるアルゴリズムは探せば出てきそうなので、ここでは、本当にそれで解けそうかを考えていきます。

一度このようなブリッジがわかれば、ブリッジ達を除いたグラフをいくつかの連結成分に分割できます。すると嬉しいのは、スタート地点(またはゴール地点)を同じ連結成分に属している節に移動させても、クエリに対する答えは変わらないということです。従って、それぞれの節はどの連結成分に属しているかさえ知っていれば十分問題に答えられそう情報が得られるということです。やはりブリッジを探すアプローチが良さそうです。

連結成分を節だと思って新しいグラフを作成すると、グラフは木になってしまいます。これは仮に島をひとつにまとめ上げる操作が可能ならば、グラフははじめは木だと思って解いても構わないということです。

残課題

ここまでで残っている課題は次のようになります。

  • ブリッジをどのように見つけるか
  • 連結成分を一つの節と思って新しいグラフを作ることはできるか?
  • ブリッジがそれぞれのクエリで何回呼ばれるか?
  • この問題のグラフが木であると仮定した時にどのように解くか?

この中で、2番目の課題は比較的簡単で、連結成分の個数を求める深さ優先探索をブリッジを用いずに行えば良いです。残りを解くことを考えます。

1つ目の課題を解く

1番目の問題は自分ではわからなかったのでRADさんの解法を参考に書きました。

リンク先のdfsという関数がこのブリッジを見つける操作に対応します。基本的には深さ優先探索です。

ある点vにつながっている枝eがブリッジかどうかを次のように判定しています。

eの方向に探索していって、すでに探索済みのノードにぶつかるかを判定する。もし既に探索済みのノードuにぶつかっていたとしたら、u→vという方向では既に探索している上で、さらにeを用いずにv→uに移動できることを意味します。これはv→u→・・・→(e)→vというループができており、すなわちeがブリッジでないことを意味します。

前述のRADさんの解法では、探索した順番に節にidを振っていき、fup[v]でvに隣接しているノードのなかでidが最も小さい節のidを格納しています。その上で、vに隣接する節をすべて探索し終わった後で、vのidとfup[v]を比較して、すでに探索済みのノードに接触したかを判定しています。

3, 4番目の課題を考える

さて、残りは3, 4番目の問題ですが、少し考えてみると問題で与えられたグラフが木だと、スタートからゴールまでどの枝を取り除いても、ゴールに到達できなくなります。つまり、この場合(クエリに対する答え)=(スタートからゴールまでの経路の長さ)です。グラフを木に限定したことで確かに問題が簡単になっているので、このグラフを木の場合に帰着させる方針は正しそうです。

すると、問題は経路長の計算を今のn, m, kの変数制限下で行えるかということです。クエリの数が節の数と同じくらいあるので、実質的に全節から全節への最短距離を求めなければならないことになりません。全節から全節への最短経路の計算というと自分の頭にはワーシャルフロイドしかなかったのですが、これではn**3かかるので間に合いません。

LCAを使って3, 4番目の課題(木の最短経路問題)を解く

ここもわからなかったので、他の方の解法を見たところ、LCA(Lowest Common Ancestor)を用いるのが一般的なようです。確かに、根から各頂点までの深さを求めれば、木の場合、経路長は(スタートの深さ)+(ゴールの深さ)-(LCAの深さ)*2となります。LCAはRMQ(Range Minimum Query)を用いて高速に解く事ができます。その詳細はTopCoderのチュートリアルなどにありますのでそちらを参照して下さい。

反省

第一歩のところで書いていたブリッジごとに値をカウントするというアプローチ(下の擬似コード参照)を取っていないことに気が付きます。

for each ブリッジ
  何らかの条件を満たす、クエリに対して答えをインクリメントする
end
for each クエリ
  クエリに対する答えを出力する
end

2011-09-20

[][] Codeforces Beta Round #87 Div1. C 23:36 はてなブックマーク -  Codeforces Beta Round #87 Div1. C - 練習帳

C. Plumber

問題文

 問題文


分析

 最上行と最左列(あわせて"端"と呼ぶ事にします)の配置の仕方が決まれば,残りのマス("内部"と呼ぶ事にします)が決まる事までは分かりました.反省点は以下のような所です.

  • 端から2つのマスを取ってきたとき,それらは独立に配置を決められるか,また決められない場合はどのくらい制限はどのくらいつくのかが分からなかった.
  • 端の配置よって,内部で事前に与えられる置き方と矛盾する場合もあれば,そうでない場合もある.それらをすべて数え上げる為には端の配置の仕方を全探索しなければならないのではないかと思ってしまった.

 敗因は端を特別視してしまった事だと思います.仮にi行目j列目のマスは配置が予め決められていたとすると,i行目のすべてのマスは1,2か3,4かが決まり,j列目の全てのマスは1,4か2,3かが決まります.従って,初期配置がすべて決まっていない行,列の数だけ選択の自由度があります.

修正コード
(#include 省略)

using namespace std;

typedef long long ll;

int table[555555];
int tablet[555555];

int n, m;

int get_char(int i, int j){
  return table[i*m+j];
}

void set_char(int i, int j, int c){
  table[i*m+j] = c;
}

int mod = 1000003;

bool is_consistent_row(int i , bool dir){
  for(int j = 0; j < m; j++){
    if( ((j % 2 == 0)^dir) && (get_char(i, j) == 3 || get_char(i, j) == 4)){
      return false;
    }else if( ( (j % 2 == 1)^dir) && (get_char(i, j) == 1 || get_char(i, j) == 2)){
      return false;
    }
  }
  return true;
}

bool is_consistent_column(int j , bool dir){
  for(int i = 0; i < n; i++){
    if( ((i % 2 == 0)^dir) && (get_char(i, j) == 1 || get_char(i, j) == 4)){
      return false;
    }else if( ((i % 2 == 1)^dir) && (get_char(i, j) == 2 || get_char(i, j) == 3)){
      return false;
    }
  }
  return true;
}

int main(){
  while(cin >> n >> m){
    memset(table, -1, sizeof(table));
    for(int i = 0; i < n; i++){
      for(int j = 0; j < m; j++){
	char c; cin >> c;
	if(c == '.'){
	  set_char(i, j, -1);
	}else{
	  set_char(i, j, c-'0');
	}
      }
    }

    int ret = 1;

    for(int i = 0; i < n; i++){
      bool try1 = is_consistent_row(i, true);
      bool try2 = is_consistent_row(i, false);
      if(!try1 && !try2){
	ret = 0;
      }
    }

    for(int j = 0; j < m; j++){
      bool try1 = is_consistent_column(j, true);
      bool try2 = is_consistent_column(j, false);
      if(!try1 && !try2){
	ret = 0;
      }
    }

    for(int i = 0; i < n; i++){
      bool is_given = false;
      for(int j = 0; j < m; j++){
	if(get_char(i, j) != -1){
	  is_given = true;
	}
      }
      if(!is_given){
	ret = (ret * 2 + mod) % mod;
      }
    }

    for(int j = 0; j < m; j++){
      bool is_given = false;
      for(int i = 0; i < n; i++){
	if(get_char(i, j) != -1){
	  is_given = true;
	}
      }
      if(!is_given){
	ret = (ret * 2 + mod) % mod;
      }
    }
    cout << ret << endl;
  }
  return 0;
}