随便玩玩系列之一:SPOJ-RNG+51nod 算法马拉松17F+51nod 1034 骨牌覆盖v3

时间:2022-06-26 18:55:20

先说说前面的SPOJ-RNG吧,题意就是给n个数,x1,x2,...,xn 每次可以生成[-x1,x1]范围的浮点数,把n次这种操作生成的数之和加起来,为s,求s在[A,B]内的概率

连续形的概率

假设有3步,那整个分布范围相当于一个立体几何图形,上界b和下界a可当成一个x+y+z=a或b的平面看待,算出x<=X1 x>=-X1 y<=X2 y>=-X2 z<=X3 z>=-X3

发现体积就是f(x1,x2,x3)+f(-x1,-x2,x3)+f(-x1,x2,-x3)+f(x1,-x2,-x3)-f(-x1,x2,x3)-f(-x1,x2,x3)-f(-x1,x2,x3)-f(-x1,-x2,-x3) (f(x1,y1,z1)指在不超上下界的前提下满足x<x1,y<y1,z<z1的所有连续点包含的体积,其实就是3条棱互相垂直的正三棱锥)

这就容斥了,不管是几维的都可以,基本思想都是一样的,搞2^n个n维棱锥容斥就是了(2维的是4个等腰直角三角形,1维的是2条直线)

然后就是悲催的算法马拉松17F题了。。。其实是道好题来的,只是出题人不知世界上还有这题,然后某大牛把思路理清后把答案直接搬了过来

那题也是类似的,几个集合任意数之和,求覆盖概率

虽说是离散+整型,其实数学思想跟上面的差不多

把另一个人的区间反转,就成了[-rx,-lx]

然后格式差不多

只不过还要算出和等于0的部分,不过真心不是问题

0平面由于都是与水平面、垂直面45度角的夹角,基本都是1/n!的系数

由于还有横向、竖向平面的上下界,容斥一下,发现又是几个三棱锥的体积差

至于怎么算出这些三棱锥的体积,其实答案就在互相垂直的棱上

经典的1*2骨牌覆盖方案数问题。。。但由于是100*100,2^m会挂

然后看那些大神证明的过程,好神奇啊

过几天我也学下好了

http://comet.51nod.com/answer/favorite.html?answerId=635&page=1

https://en.wikipedia.org/wiki/FKT_algorithm

http://blog.sina.com.cn/s/blog_6827adcf0100z7pj.html

https://www.wikiwand.com/en/FKT_algorithm

关于题目本身的问题。。。

随便玩玩系列之一:SPOJ-RNG+51nod 算法马拉松17F+51nod 1034 骨牌覆盖v3

感觉就是用这个式,然后高精度+倍角公式+泰勒展开+和/差角公式乱搞