有n个男孩和n个女孩需要配对。只有男孩i和女孩j相容时，它们才会配对。给定它们兼容性的邻接矩阵，找到可以成对模1e9 + 7的成对方式。
示例
输入（控制台）：
3
111
101
110
输出（控制台）：
3
n <= 24，并且在Linux上的时间限制为0.5秒。
我想出了一个n ^ 2 * 2 ^ n解决方案，但它超过了n> 20的时间限制。因此需要一个n * 2 ^ n解决方案，如果可能的话甚至可能需要2 ^ n。
#include <iostream>
#include <vector>
using namespace std;
int main()
{
static const int mod = 1000000009;
int n;
char x;
scanf("%d", &n);
vector<vector<int>> b(n);
vector<int> m(1 << n);
m[0] = 1;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
{
x = getchar_unlocked();
x = getchar_unlocked();
if (x == '1')
b[i].emplace_back(j);
}
for (int i = 0; i < n; ++i)
for (int j = (1 << n) - 1; j >= 0; --j)
for (const auto& x : b[i])
if ((j & (1 << x)) == 0)
{
auto t = j | (1 << x);
m[t] += m[j];
if (m[t] >= mod)
m[t] -= mod;
}
cout << m[(1 << n) - 1];
}
想象您有示例矩阵：
111
101
110
您正在查看的是要选择的n 1个值的选择，因此没有行或列有两个选择。
有三个有效的解决方案：
100 010 001
001 001 100
010 100 010
快速计数的方法是遍历第一行，例如最上面的一行，并为每个1值（在下面标记为*），添加存在的方式来填充子矩阵而不选择行和列：（我用-屏蔽了）
*--
-01
-10
我们正在寻找的值是“ 01 10条路的数量”
-*-
1-1
1-0
“加上11 10路的数量”
--*
10-
11-
“加上10 11路的数量”
现在，您需要将解决方案缓存到“ 11 10路的数量”形式的子问题。而且，如果您对矩阵进行行/列排序，您会发现
“ 11 10通道数”和“ 11 10通道数”是相同的精确值。 （1）
并且“ 01 10方式的数目也为1。所以，1 + 1 + 1 = 3。
因此，您将执行n子问题，该子问题将查找n-1子问题的值，这将.... 1问题。需要的更差的缓存大小是2 ^ n（用于选择不同的行），但是排序会使它更小。
要在0.5秒内解决24大小的问题，您将需要高效的结构，例如位模式以将完整行存储在单个int中。对于上述方法，我使用单个std :: string进行了快速定位，并在不到5秒的时间内随机运行了20x20。因此，您可以为您完成工作。
您能否说出这是哪个竞争性编程网站，一旦我对其进行优化，就想检查该解决方案是否通过。 ：-）