t*******e 发帖数: 1633 | 1 1. 6 digits number, each changes from 0 to 9. Find the odds that sum of
first three is the same as the sum of last three.
大牛han6曾给出如下解答, 无奈小弟实在看不懂,哪位高人能出来详细解答一下
另小弟明早Bloomberg onsite, 请各位等我面经
发信人: han6 (周瑜), 信区: JobHunting
标 题: Re: 问几个brain teaser
发信站: BBS 未名空间站 (Tue Sep 28 14:46:27 2010, 美东)
每一个数字都是0~9的iid
一个数字的情况,总和为0~9的方法分别为
1, 1, 1, 1, 1, 1, 1, 1, 1, 1
两个数字的情况,总和为0~18的方法为以上的卷积
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
三个数字的情况,总和为0~27的方法为以上的卷积
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 63, 69, 73, 75, 75, 73, 69, 63, 55,
45,
36, 28, 21, 15, 10, 6, 3, 1
然后计算平方和为:55252
则概率为 55252/1000000
如果考官要你推广到m进制的n个数字相等(前后共2n个数字)
那么,可以告诉他,或者她:
利用 FFT 进行 logn 次卷积,其中最长的一次长度为 mn/2
总复杂度为:mnlog(mn)logn
不用FFT的话,由于卷积的特殊性,可以达到mn^2,考虑 FFT 的额外开销,实际速度可
能相差不
大。
如果这是一个二进制的问题,即每个数字只能是 0 或 1。那么无论多少个数
字都可以很容易的求出结果,因为其历次卷积得到了杨辉三角。
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1 | s*******r 发帖数: 47 | 2 我的理解是: 6位数总的排列是1000000(10^6)
两头相等的可能排列就是:
三个数字的情况,总和为0~27的方法为以上的卷积
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 63, 69, 73, 75, 75, 73, 69, 63, 55,
45,
36, 28, 21, 15, 10, 6, 3, 1
每种和的情况的排列有: x*x, 比如和为4,那么就有10x10种排列,
总的排列就是他说的“计算平方和为:55252” | t*******e 发帖数: 1633 | 3
我再看看,多谢
【在 s*******r 的大作中提到】 : 我的理解是: 6位数总的排列是1000000(10^6) : 两头相等的可能排列就是: : 三个数字的情况,总和为0~27的方法为以上的卷积 : 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 63, 69, 73, 75, 75, 73, 69, 63, 55, : 45, : 36, 28, 21, 15, 10, 6, 3, 1 : 每种和的情况的排列有: x*x, 比如和为4,那么就有10x10种排列, : 总的排列就是他说的“计算平方和为:55252”
|
|