algorithm - 计算整数四倍数

我今天看到这个问题，我们需要计算
整数的四倍
(X1, X2, X3, X4)，使得Li≤Xi≤Ri为i
=1、2、3、4和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

我最初的想法是
包容排除原则
我能找到无限制的四倍数，但我不知道如何找到剩下的条件，以达到最终的解决方案我也知道这个问题可以用dfs来解决。
我们如何在包含排除/DFS的情况下解决这个问题

最佳答案

包含/排除会给你四倍的数量，但不会给你四倍的数量。
设Ai是满足所有j的Lj

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

我不知道在这种方法中深度优先搜索和它有什么关系。

关于algorithm - 计算整数四倍数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30353696/