Description

铭铭有 \(n\) 个十分漂亮的珠子和若干根颜色不同的绳子. 现在铭铭想用绳子把所有的珠子 连接成一个整体.

现在已知所有珠子互不相同, 用整数 \(1\) 到 \(n\) 编号. 对于第 \(i\) 个珠子和第 \(j\) 个珠子, 可以选择不用绳子连接, 或者在 \(c_{i,j}\) 根不同颜色的绳子中选择一根将它们连接. 如果把珠子看作点, 把绳子看作边, 将所有珠子连成一个整体即为所有点构成一个连通图. 特别地, 珠子不能和自己连接.

铭铭希望知道总共有多少种不同的方案将所有珠子连成一个整体. 由于答案可能很大, 因此 只需输出答案对 \(1000000007\) 取模的结果.

Input

标准输入. 输入第一行包含一个正整数 \(n\), 表示珠子的个数. 接下来 \(n\) 行, 每行包含 \(n\) 个非负整数, 用空格隔开. 这 \(n\) 行中, 第 \(i\) 行第 \(j\) 个数为 \(c_{i,j}\).

Output

标准输出. 输出一行一个整数, 为连接方案数对 \(10^9+7\) 取模的结果.

Sample Input

3
0 2 3
2 0 4
3 4 0

Sample Output

50

Data Range

对于 100% 的数据,\(n \in \mathbb{Z^+}, 0 \leq c_{i,j} \leq 10^9+7, c_{i,j} = c_{j,i}\); 每组数据的 \(n\) 值如下表所示.

ID 1 2 3 4 5 6 7 8 9 10
\(n\) 8 9 9 10 11 12 13 14 15 16

Explanation

有点类似区间动规的子集动规, 但是其实写法更像状压动规......

因为其实就是状态压缩==

如果连这种 SB 题都不会写那还有什么信心去省选 QwQ

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
using namespace std;
typedef long long lli;
const int maxN = 20, maxn = 70000; // 65536 max
const lli modr = 1000000007;

#define bin(__x) (1<<(__x))
int n;
lli c[maxN][maxN], dp[maxn], all[maxn];

int main(int argc, char** argv)
{
    scanf("%d", &n);
    rep(i, 1, n) rep(j, 1, n)
        scanf("%lld", &c[i][j]);
    // Dynamic programming with wubsets.
    for (int k = 1; k < bin(n); k++) {
        dp[k] = 1;
        // Connecting amongst the subset itself.
        for (int i = 1; i <= n; i++) if (k & bin(i-1))
            for (int j = 1; j < i; j++) if (k & bin(j-1))
                dp[k] = dp[k] * (c[i][j] + 1) % modr;
        // Finding subsets
        all[k] = dp[k];
        for (int i = k^(k&-k), j = i; j > 0; j = (j-1)&i)
            dp[k] = (dp[k] - all[j] * dp[k^j] % modr + modr) % modr;
    }
    // Result calculated.
    printf("%d\n", dp[bin(n) - 1]);
    return 0;
}