No.1560 majority x majority
noya2
37zigen
nok0Problem Statement
Noya is a dictator who admires democracy. Having learned about the system of majority voting and become interested in it, Noya decided to immediately try holding majority votes in the assembly.
The assembly consists of $N$ members, numbered $1,2,\dots ,N$, and majority votes are held on $M$ agenda items, numbered $1,2,\dots ,M$.
You are given a table with $N$ rows and $M$ columns representing each member's position on each agenda item. Let $S_{ij}$ denote the entry in row $i$ and column $j$. $S_{ij} = 1$ means that member $i$ is in favor of agenda item $j$, and $S_{ij} = 0$ means that the member is against it.
Majority votes will now be held on the $M$ agenda items, and the order of the agenda items to be voted on is determined randomly.
However, no vote is held more than once on the same agenda item. Each agenda item is passed if at least half of the people participating in the vote on that item are in favor, and is rejected if fewer than half are in favor.
Now, since Noya does not really understand democracy, each time a majority vote is held, Noya revokes the voting rights of the members whose opinion is opposite to the decided outcome.
Members whose voting rights have been revoked cannot participate in any subsequent votes.
There are $M!$ possible orders in which the agenda items can be voted on. Among them, find the number of orders such that all agenda items are passed when the votes are held in that order.
Constraints
Input
$N\ M$
$S_{11}\dots S_{1M}$
$\vdots \qquad \qquad \vdots$
$S_{N1}\dots S_{NM}$
Output
Output the number of orders satisfying the condition of the problem.
Print a newline at the end.
Sample
Sample 1
Input
6 3 1 1 1 1 0 1 0 0 1 1 0 1 0 1 0 1 1 0
Output
2
The assembly consists of $6$ members, and majority votes are held on $3$ agenda items.
Consider holding the votes in the order of agenda items $1,2,3$.
First, in the vote on agenda item $1$, $4$ out of $6$ people are in favor, so it is passed.
Members $3,5$, who were against it, can no longer participate in subsequent votes.
Next, in the vote on agenda item $2$, $2$ out of $4$ people are in favor, so it is passed.
Members $2,4$, who were against it, can no longer participate in subsequent votes.
Finally, in the vote on agenda item $3$, $1$ out of $2$ people is in favor, so it is passed.
Note that an item is passed when the numbers of people in favor and against are equal.
Other orders also work: for example, holding the votes in the order of agenda items $2,1,3$ also results in all agenda items being passed.
These $2$ orders are the only ones in which all agenda items are passed, so output $2$.
Sample 2
Input
5 2 1 1 1 0 1 0 0 1 0 1
Output
0
In any order of voting, the agenda item voted on last is rejected.
Sample 3
Input
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
Output
0
The members seem to be in favor of nearly every agenda item, but it never happens that all agenda items are passed.
Sample 4
Input
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
Output
720
Sample 5
Input
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
Output
12404
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。