3.# 联盟
## 题目描述
在国际会议上，共有 n*n* 个国家需要加入三个联盟中的一个。任何两个接壤的国家不能加入相同的联盟。现在给出各国的接壤情况，请计算存在多少种合法的联盟分配方案。
## 输入格式
· 第一行：单个整数 n*n* 表示国家数量
· 第二行到第 n*n* 行：在第 i+1*i*+1 行有 n−i*n*−*i* 个整数 ci,i+1,ci,i+2,…,ci,n*ci*,*i*+1,*ci*,*i*+2,…,*ci*,*n*，其中
· ci,j=0*ci*,*j*=0 表示 i*i* 号国家与 j*j* 号国家不接壤
· ci,j=1*ci*,*j*=1 表示 i*i* 号国家与 j*j* 号国家接壤
## 输出格式
单个整数：表示合法的联盟分配方案总数。
## 输入样例#1
3
1 1
1
## 输出样例#1
6
## 输入样例#2
4
1 1 1
1 1
1
## 输出样例#2
0
## 说明提示
数据范围
· 对于 50%50% 的数据，1≤n≤121≤*n*≤12
· 对于 100%100% 的数据，1≤n≤201≤*n*≤20
样例1说明
三国两两接壤，形成三角形。三个联盟的排列方案为 3!=63!=6 种。
## 限制
时间限制：1000ms
内存限制：512MiB

本题需要计算在有 n 个国家的情况下，满足条件的联盟分配方案的总数。其中，需要满足的条件是任何两个接壤的国家不能加入相同的联盟。我们可以使用动态规划或递归加剪枝的方法来解决这个问题。

动态规划的思路是，我们可以先考虑较小的国家数量，然后逐步增加国家数量，计算每个状态下的联盟分配方案数。对于每个状态，我们需要保存已经计算过的结果，避免重复计算。具体的状态转移方程和算法实现需要仔细考虑和调试。

递归加剪枝的思路是，我们可以从第一个国家开始，依次考虑每个国家的联盟分配情况。对于每个国家，我们可以选择加入任何一个联盟，然后递归处理剩下的国家。在递归的过程中，我们需要剪枝，即当发现当前情况下无法满足条件时（比如已经有两个接壤的国家加入了同一个联盟），就停止递归。这种方法的实现也需要仔细思考和调试，以防止出现死循环或者计算错误的情况。

由于本题的数据规模较小（国家数量 n 最大为 20），还可以使用暴力枚举的方法来解决。我们可以枚举所有可能的联盟分配方案，然后判断每种方案是否满足条件。虽然这种方法的时间复杂度较高，但在数据规模较小的情况下仍然可以解决问题。

无论使用哪种方法，都需要仔细处理边界情况和特殊情况，确保程序的正确性和效率。此外，由于本题的时间限制和内存限制较为严格，优化算法的效率也是非常重要的。