VNPLAN2 - Uplan
Bài này là bài V11PLAN với giới hạn N lớn hơn.
Note: this is V11PLAN with higher limit for N.
In 2011, Vietnam sets out a national development plan. The plan will consist of two phases: the first half of the year and the second half of the year. At each phase, a number of paths between some pairs of cities will be built.
You are given a graph describle the result of the plan, in which each edge (i,j) represents the plan to make city i and city j connected (not necessarily directly). You need to count the number of different plans that can produce that graph. Two plans are different if there is a road being built in a phase of the plan but not built in the corresponding phase of the other plan.
For example, if we build in the first phase road (1,2) , and then in the second phase we build (2,3) , the resulting graph will have three edges: (1,2), (2,3), (1,3). Building (1,2) in the first phase and (1,2), (1,3) in the later phase produce the same result. Note, we can only build a road between a pair of cities in a phase, but at the later phase we can rebuild that route again due to subsidence rate in Vietnam is pretty fast.
Input
The first line is N (1 <= N <= 80).
N lines follow, each has N integers. City i and j should be connected at the end of the year if the j-th number at line i is 1, else it's 0. The input will make sure that is city i and j are connected, j and k are connected, then i and k are connected.
Output
A single integer which is the number of different plans modulo 1000000007.
Example
Input: 2 0 1 1 0 Output: 3
Explain: we can build the road between two cities only in the first haft of the year, second half of the year, or both.
Input: 3 0 1 1 1 0 1 1 1 0 Output: 54
Input: 16 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 Output: 604876153
hide comments
Mitch Schwartz:
2014-09-23 16:59:01
Problem moved to partial because of scoring. Email sent to problem setter to inform. |
|
Min_25:
2014-09-23 16:59:01
This problem is solvable even if 1 <= N <= 1000. |
Added by: | ɐoɥuɐʌ |
Date: | 2013-11-30 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Original problem is V11PLAN - Khuc Anh Tuan |