找到生成 N 对唯一的课程而没有冲突的方法的数量

Question

我遇到了这个问题，想不出好的解决办法。问题如下

有 N 门 CS 课程和 N 门 EEE 课程，编号均为 1, 2, ... , N.

对于每个i，j（1≤i，j≤N），CS课程i和EEE课程j的兼容性作为整数Aij给出。如果 Aij = 1，CS 课程 i 和 EEE 课程 j 不冲突；如果 Aij = 0，它们会发生冲突。

Ravan 正在尝试制作 N 对，每对包含不冲突的 CS 课程和 EEE 课程。这里，每门CS课程和每门EEE课程必须恰好属于一对。

求 Ravan 可以组成 N 对的方式数，模 10^9 + 7。

Ex.

0 1 1
1 0 1
1 1 1

res : 3
Explanation 
Here there are 3 ways to make pairs:

(1,2),(2,1),(3,3)

(1,2),(2,3),(3,1)

(1,3),(2,1),(3,2)

Where (i,j) is pair of CS i course and EEE j course

为了解决上述问题，我编写了一个简单的dfs函数，但它似乎不正确。这也是一个非常缓慢的实现。我的方法如下：

int counter=0;

void dfs(vector<vector<int>>&nums, int n, vector<bool>&visit, int c){
    
    if(c == n-1){
        counter++;
        return;
    }
    
    for(int i=0; i<n; i++){
        if(nums[i][c]==0 || visit[i])continue;
        visit[i] = true;
        dfs(nums, n, visit, c+1);
        visit[i] = false;
    }
    
}

void solve(vector<vector<int>>&nums, int n){
    vector<bool>visit(n, false);
    dfs(nums, n, visit, 0);
    cout << counter%1000000007;
}

对于这个问题，我的思考方向是否正确？还可以做些什么来解决这个问题并且效率太高？任何帮助都是有价值的。谢谢！

Answer 1

这只是@amit 评论的扩展，看起来像 Inclusion-Exclusion。

首先我们计算 N 对的方法数。这就是 N!。在您的示例中，这是 6.

all sets of pairs
(1, 1), (2, 2), (3, 3)
(1, 1), (2, 3), (3, 2)
(1, 2), (2, 1), (3, 3)
(1, 2), (2, 3), (3, 1)
(1, 3), (2, 1), (3, 2)
(1, 3), (2, 2), (3, 1)

然后对于我们不想要的每一对，我们减去制作 N 对的方法数，包括那个被禁止的对。这是这样的对数乘以(N-1)!。在您的示例中，这是 4。（2 对，每对在 2 组 N 对中。）

Contains forbidden pair (1, 1)
(1, 1), (2, 2), (3, 3)
(1, 1), (2, 3), (3, 2)

Contains forbidden pair (2, 2)
(1, 1), (2, 2), (3, 3)
(1, 3), (2, 2), (3, 1)

但是制作 N 对（包括 2 个禁止对）的方法现在已经减去两次。（也就是我们加了一次(1, 1), (2, 2), (3, 3)，减了两次，现在用-1算了。）所以我们需要把它们加回去。加1回来：

Contains both forbidden pairs (1, 1), (2, 2)
(1, 1), (2, 2), (3, 3)

如果有一组 3 个禁用对，我们必须将它们重新添加进去。但是没有。所以我们最后的计算是：

6 - (2 + 2) + 1

根据需要给出 3。

那么对更大的 N 进行此计算怎么样？那么我们知道如何计算N!、(N-1)!、(N-2)!等等。棘手的一点是有多少禁止对，2对，3对等等。

为此我们可以使用动态规划。构建一个 dp，使得 dp[k][l] 是 l 对 (i, j) 的集合的数量，它们可以一起出现在 i <= k 的作业中。我们从 dp[0] = [1, 0, 0, ...] 开始。 dp[N] 将为您提供所有可以分配在一起的每种大小的禁止对的数量。

在您的示例中，该结构应该结束：

dp = [
    [1, 0, 0, 0],
    [1, 1, 0, 0],
    [1, 2, 1, 0],
    [1, 2, 1, 0],
]

我们从中得到计算

3! * dp[3][0] - 2! * dp[3][1] + 1! * dp[3][2] + 0! * dp[3][3]
  = 6 * 1 - 2 * 2 + 1 * 1 - 1 * 0
  = 3

这应该足以让你继续前进。

找到生成 N 对唯一的课程而没有冲突的方法的数量

Find the number of ways to generate N unique pairs of courses without clashes

c++

algorithm

matrix

depth-first-search