No.1560 majority x majority
タグ : / 解いたユーザー数 60
作問者 :
noya2
/ テスター :
37zigen
nok0
問題文
noya君は民主主義に憧れる独裁者です。多数決という制度を知って興味を持ったnoya君は議会で早速多数決をとってみることにしました。
議会は議員 $1,2,\dots ,N$ の $N$ 人で行われ、議題 $1,2,\dots ,M$ の $M$ 個の議題について多数決を行います。
各議員の各議題に対する賛否を表す $N$ 行 $M$ 列の表が与えられます。$i$ 行 $j$ 列目を $S_{ij}$ と表すことにすると、 $S_{ij} = 1$ ならば議員 $i$ が議題 $j$ に賛成であり、$S_{ij} = 0$ ならば反対であることを表しています。
これから $M$ 個の議題について多数決が行われますが、多数決をとる議題の順番はランダムに決まります。
ただし、同じ議題で多数決が行われることはありません。また、それぞれの議題は、その議題の多数決に参加した人数の半数以上の賛成で可決、 半数未満の賛成で否決されます。
さて、noya君は民主主義をよくわかっていないので、多数決が行われるたびに、 決定した可否と反対の意見を持つ議員の多数決の参加権を剥奪してしまいます。
多数決の参加権を剝奪された議員は、それ以降の多数決に参加できません。
多数決を行う議題の順番は全部で $M!$ 通りありますが、このうち、 その順番で多数決が行われたときすべての議題が可決されるものが何通りあるか求めてください。
制約
入力
$N\ M$
$S_{11}\dots S_{1M}$
$\vdots \qquad \qquad \vdots$
$S_{N1}\dots S_{NM}$
出力
題意を満たすようなものが何通りあるかを出力してください。
最後に改行してください。
サンプル
サンプル1
入力
6 3 1 1 1 1 0 1 0 0 1 1 0 1 0 1 0 1 1 0
出力
2
議会は $6$ 人の議員で行われ、 $3$ 個の議題について多数決が行われます。
議題 $1,2,3$ の順で多数決を行うことを考えます。
まず、議題 $1$ で多数決を行うと、$6$ 人中 $4$ 人が賛成なので可決されます。
また、このとき反対していた議員 $3,5$ は、以降の多数決に参加できなくなります。
次に、議題 $2$ で多数決を行うと、$4$ 人中 $2$ 人が賛成なので可決されます。
また、このとき反対していた議員 $2,4$ は、以降の多数決に参加できなくなります。
最後に、議題 $3$ で多数決を行うと、$2$ 人中 $1$ 人が賛成なので可決されます。
賛成、反対の人数が同じ場合は可決されることに注意してください。
これ以外の順でも、例えば議題 $2,1,3$ の順で多数決を行っても、すべての議題が可決されます。
すべての議題が可決されるような順番は以上の $2$ 通りなので $2$ を出力します。
サンプル2
入力
5 2 1 1 1 0 1 0 0 1 0 1
出力
0
どの順番で多数決を行っても、最後に多数決を行った議題は否決されます。
サンプル3
入力
5 5 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1
出力
0
議員は概ねどの議題についても賛成のようですが、すべての議題が可決されることはありません。
サンプル4
入力
6 6 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1
出力
720
サンプル5
入力
18 8 1 1 0 1 0 1 1 0 0 0 0 1 1 1 1 1 0 0 1 0 1 0 1 1 0 1 1 1 0 0 1 0 0 0 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 0 0 1 0 1 0 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 0 1 0 1 0 0 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 0 0 1
出力
12404
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。