Kế hoạch phát triển

View as PDF

Submit solution

Points: 0.91 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VNOI Online 2011Tác giả: Khúc Anh Tuấn
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Năm ~2011~, Việt Nam đề ra một kế hoạch phát triển đất nước. Bản kế hoạch sẽ gồm ~2~ giai đoạn: đầu năm và cuối năm. Ở mỗi giai đoạn, một số con đường nối giữa các cặp thành phố sẽ được xây dựng.

Bạn được cho một đồ thị thể hiện kết quả của kế hoạch, trong đó mỗi cạnh ~(i, j)~ thể hiện bản kế hoạch đã tạo ra một đường đi giữa thành phố ~i~ và thành phố ~j~ (không cần thiết phải là đường đi trực tiếp). Bạn cần đếm số lượng bản kế hoạch khác nhau có thể cho ra kết quả trên. Hai bản kế hoạch khác nhau nếu có một con đường được xây ở một giai đoạn của bản kế hoạch này nhưng không được xây ở giai đoạn tương ứng của bản kế hoạch kia.

Ví dụ, nếu giai đoạn đầu ta xây dựng đường nối ~(1, 2)~, giai đoạn sau ta xây dựng đường nối ~(2~, ~3)~ thì đồ thị kết quả sẽ có ~3~ cạnh: ~(1, 2)~, ~(2, 3)~, ~(1, 3)~ do tồn tại đường đi giữa cả ~3~ thành phố này. Nếu ta xây ~(1, 2)~ vào giai đoạn đầu và xây ~(1, 2)~, ~(1, 3)~ vào giai đoạn sau, ta thu được cùng một kết quả. Lưu ý, để tiết kiệm, ta chỉ có thể xây thêm một con đường nối một cặp thành phố trong một giai đoạn, nhưng giai đoạn sau ta có thể xây thêm một con đường nữa để thay thế do tốc độ lún sụt đường ở Việt Nam là khá nhanh.

Input

  • Dòng đầu ghi số ~N~ thể hiện số thành phố. ~(1 \le N \le 7)~
  • ~N~ dòng sau, mỗi dòng ghi ~N~ số 0/1 thể hiện ma trận kề của đồ thị kết quả. Số ~1~ thể hiện giữa ~2~ thành phố tương ứng có đường đi. Đồ thị được cho luôn đúng đắn: nếu có đường đi giữa ~i~ và ~j~ thì sẽ có cạnh giữa ~i~ và ~j~.

Output

  • Một số duy nhất thể hiện số lượng bản kế hoạch khác nhau.

Sample Input

2
0 1
1 0

Sample Output

3

Note

Giải thích: Bạn có thể xây đường nối giữa 2 thành phố ở giai đoạn đầu, giai đoạn sau hoặc cả 2 giai đoạn.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.