被问到上次ZOJ Monthly中的H题Special Special Judge III怎么用容斥原理做。确实我只在解题报告中提了一句可以这么做，然后就丢下了一段python代码跑了。现在来详细解释一下如何运用容斥原理求一个Hyperrectangle被Hyperplane切割后剩余部分的体积。这里假定n维空间内的Hyperrectangle为

而对应的Hyperplane为

那么我们实际要求的就是Convex

的体积。

不妨先考虑两个二维平面上的例子：

此时的答案是

此时的答案是

之所以要加上是因为它在和中被减掉了两次，多减了一次，需要加回来。如果考虑在第一个例子中的话，就有对任何情况，这个公式都成立。

这里，我们已经用上了容斥原理。现在尝试推广到n维的情况。首先，在高维空间里，这里就不再是三角形的面积了，而是单纯形(Simplex)的体积，单纯形

在b≤0时体积显然为0，而当b>0时，体积为，不要忘了除以n!。那么我们要求的体积实际上就是很多个相似的（也就是b不同）的单纯形的和差。这些单纯形的顶点就是原先Hyperrectangle的顶点，一个n-Hyperrectangle有2ⁿ个顶点，可以用二进制数k来表示，如果第j位为0，则代表x_j=0，否则x_j=X_j，那么对应的单纯形是

等价于

知道了这2ⁿ个单纯形的体积后，剩下的问题就是我们应该加上还是减去这个单纯形的体积。这个问题由容斥原理(Inclusion–exclusion principle)来回答：如果二进制数k里有偶数个1，那么取正号，否则取负号。这样来看这个三维的例子（更高维的图我可画不出来……）：

由前面推导知道，答案应该是

现在再贴上这段python代码应该很清楚了吧：

def gao(n, a, x, b0):
	ret = 0
	for i in range(2 ** n):
		b = b0
		c = 0
		for j in range(n):
			if i & (1 << j):
				b -= a[j] * x[j]
				c += 1
		if b <= 0:
			continue
		if c % 2:
			ret -= pow(b, n)
		else:
			ret += pow(b, n)
	for i in range(n):
		ret /= (i + 1) * a[i]
	return ret

if __name__ == '__main__':
	print gao(3, [1, 1, 1], [2, 4, 6], 7.0)

最后，SPOJ的2002. Random Number Generator (RNG)就是这样一道a_i=1情况下的体积比问题。贴上我AC的cpp代码和超时的ruby代码。

source code (RNG.cpp)
source code (RNG.rb)

This entry was posted on Sunday, October 10th, 2010 at 12:27 am and is filed under summary. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.