algorithm - 计算四元组整数的个数

Question

I saw this question today where we need to count the number of quadruples of integers (X1, X2, X3, X4), such that Li ≤ Xi ≤ Ri for i = 1, 2, 3, 4 and X1 ≠ X2, X2 ≠ X3, X3 ≠ X4, X4 ≠ X1.

    input:
     Li Ri
     1  4 
     1  3 
     1  2 
     4  4

output:
8

1 2 1 4
1 3 1 4
1 3 2 4
2 1 2 4
2 3 1 4
2 3 2 4
3 1 2 4
3 2 1 4

我最初的想法是使用

Principle of Inclusion Exclusion

我能够找到 number if unrestricted quadruples 但我无法弄清楚我们如何才能找到剩余的条件来达到最终解决方案。我也开始知道这个问题可以使用 DFS 来完成。

我们如何使用 Inclusion Exclusion/DFS 来做这道题

Answer 1

包含/排除会给你四倍数，但不会给你四倍本身。

设 Ai 是满足所有 j 的 Lj<=Xj<=Rj 的四元组集合，其中 Xi=X(i+1)(其中索引是循环的，因此 X5 表示 X1)。在您提供的示例中，

A1 = { (1114), (1124), (2214), (2224), (3314), (3324) }
A2 = { (1114), (2114), (3114), (4114), (1224), (2224), (3224), (4224) }
A3 = { } (empty set)
A4 = { (4114), (4214), (4314), (4124), (4224), (4324) }

我们还需要集合对的交集:

A1 cap A2 = { (1114), (2224) } (note first three numbers identical)
A1 cap A3 = { }
A1 cap A4 = { } (can't have X4=X1=X2)
A2 cap A3 = { }
A2 cap A4 = { (4114), (4224) }
A3 cap A4 = { }

三元组的交集:

A1 cap A2 cap A3 = { }
A1 cap A2 cap A4 = { }
A1 cap A3 cap A4 = { }
A2 cap A3 cap A4 = { }

所有集合的交集:

A1 cap A2 cap A3 cap A4 = { }

Inclusion/exclusion以其互补形式告诉我们

|intersection of complements of Ai| = |unrestricted quadruples| 
- sum of |Ai| + sum of |Ai cap Aj| - sum of |Ai cap Aj cap Ak| 
+ sum of |Ai cap Aj cap Ak cap Al|

其中索引 i、j、k、l 都不相等。在你的例子中，

|intersection of complements of Ai| = 4x3x2x1 - (6+8+0+6) + (2+0+0+0+2+0) - (0+0+0+0) + 0 
= 24 - 20 + 4 - 0 + 0 = 8

为了找到|Ai|及其交点，您必须找到区间 [Li,Ri] 的交点，并将交点的长度乘以不受限制的区间的长度。例如，

|A1| = |[1234] cap [123]| x |[12]| x |[4]| = 3 x 2 x 1 = 6
|A2 cap A4| = |[123] cap [12]| x |[4] cap [1234]| = |[12]| x |[4]| = 2 x 1 = 2

在这种方法中，我看不出深度优先搜索与它有什么关系。