Oct
10
2010


用容斥原理计算被Hyperplane切割后的Hyperrectangle体积
Posted by watashi in summary, tags: hyperspace, SPOJ, 容斥原理被问到上次ZOJ Monthly中的H题Special Special Judge III怎么用容斥原理做。确实我只在解题报告中提了一句可以这么做,然后就丢下了一段python代码跑了。现在来详细解释一下如何运用容斥原理求一个Hyperrectangle被Hyperplane切割后剩余部分的体积。这里假定n维空间内的Hyperrectangle为
而对应的Hyperplane为
那么我们实际要求的就是Convex
的体积。
不妨先考虑两个二维平面上的例子:
此时的答案是
此时的答案是
之所以要加上
这里,我们已经用上了容斥原理。现在尝试推广到n维的情况。首先,在高维空间里,这里就不再是三角形的面积了,而是单纯形(Simplex)的体积,单纯形
在b≤0时体积显然为0,而当b>0时,体积为
等价于
知道了这2n个单纯形的体积后,剩下的问题就是我们应该加上还是减去这个单纯形的体积。这个问题由容斥原理(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)就是这样一道ai=1情况下的体积比问题。贴上我AC的cpp代码和超时的ruby代码。
为啥
p /= x[i] * (i + 1);
而不是
p/=x[i]*2*(i+1)
shi哥的latex插件是不是挂了? 看不到公式了呢。。。
囧,看了下用的是http://s.wordpress.com/latex.php的,必须是被墙掉了?
。。。 挂上vpn之后发现看到了。。 如shi哥所想。。。。
配置里只能选用wordpress的或者本地的,不能设置为第三方的,于是暂时不管了= =b
有空再来折腾……
我很好奇当年为什么看得到。。 那时候wordpress.com没被墙?
SPOJ的2002. Random Number Generator (RNG) 题目给的随机数范围是 -xi 到 xi,请问是怎么转化成0 到 xi 来求解的
也就是你代码中的这段,理解不了啊….
p = 1;
y = 0;
for (int i = 0; i < n; ++i) {
scanf("%Lf", &x[i]);
p /= x[i] * (i + 1);
y += x[i];
}
a = (a + y) / 2;
b = (b + y) / 2;
如果变成任意的 p到q ,又该怎么转化呢?
就是平移一下?
还是不明白啊,它怎么就实现平移了呢?
就是坐标变换啊,对计算完全没有影响
请问为什么体积∏(b/ai)/n! ?
单纯型的体积就是可以这么算的啊,你要证明可以关于维度用数学归纳法……
pow(b, n) 是什么意思
b的n次方
Shi哥太给力了