j******s
发帖数: 48 | 1 在网上到是找到个解法
http://hackerrank.blogspot.com/2013/03/arithmetic-progression.h
不过完全不知道如何Handle这种题，感觉是纯数学的东西，各位大神都是如何练这种类
型的题的？诚心请教！ |
s********9
发帖数: 586 | 2 我觉得hackerrank有些题不适合面试用，这类题光是面试官解释起来就得花个十分钟 |
j******s
发帖数: 48 | 3 纯粹想把这道题解决了而已，权当锻炼思维。
【在 s********9 的大作中提到】
: 我觉得hackerrank有些题不适合面试用，这类题光是面试官解释起来就得花个十分钟
|
b********n
发帖数: 29 | 4 花了两个礼拜才做出来。。。各种查资料。。。
数学上面，得到恒定差的次数是p_1+...+p_n, 得到的定差结果是d1^p1*d2^p2...*dn^
pn*(p1+..._pn)!
这个公式可以通过自己手推，把2个等差数列乘起来，你会发现求两次差就可以得到定
值，把3个乘起来，...一直到把n个乘起来，得到的求差次数是一个和式（在这个网页
里面有http://www.mymathforum.com/viewtopic.php?f=40&t=7993）而这个和式正好等于(p1+...+pn)!
下面的问题就在于提高运算效率，有三点
第一点就是如何maintain任何一个区间里的(p1+...+pn)和d1^p1*...*dn^pn. 这个因为
是range query，用segment tree得到，可以得到lg(n)的update和query time.如果每
次query都需要求一遍和的话，需要O(n)时间，如果提前算prefix sum的话，query是O(
1)，可是update v需要O(n)，所以两种方法都会超时，必须同时有O(lgn)的update和
query time才行。
segment tree是从这个人的博客里学到的http://se7so.blogspot.com/2013/01/arithmetic-progression.html
第二点，算阶乘不要每次query都算，最后积累在一起，直接算到最大的数，把中间结
果存起来。注意当p1+...+pn>1000003时，阶乘求模就是0.
第三点，做指数求模要用这个快速方法：
http://en.wikipedia.org/wiki/Modular_exponentiation
这题做得我走火入魔了，就耽搁了不少时间，其实对准备面试来说，确实是得不偿失。
但是做出来了以后觉得提高还是挺大的。
期待ACM的大牛们可能有更简单的解释。 |
j******s
发帖数: 48 | 5 谢谢分享！感激不尽！
O(
【在 b********n 的大作中提到】
: 花了两个礼拜才做出来。。。各种查资料。。。
: 数学上面，得到恒定差的次数是p_1+...+p_n, 得到的定差结果是d1^p1*d2^p2...*dn^
: pn*(p1+..._pn)!
: 这个公式可以通过自己手推，把2个等差数列乘起来，你会发现求两次差就可以得到定
: 值，把3个乘起来，...一直到把n个乘起来，得到的求差次数是一个和式（在这个网页
: 里面有http://www.mymathforum.com/viewtopic.php?f=40&t=7993）而这个和式正好等于(p1+...+pn)!
: 下面的问题就在于提高运算效率，有三点
: 第一点就是如何maintain任何一个区间里的(p1+...+pn)和d1^p1*...*dn^pn. 这个因为
: 是range query，用segment tree得到，可以得到lg(n)的update和query time.如果每
: 次query都需要求一遍和的话，需要O(n)时间，如果提前算prefix sum的话，query是O(
|
l***z
发帖数: 9 | 6 昨天卡了三个小时没做出来。。。
真是好心人啊，可算知道怎么做了
这种题确实对面试用处不大，不过当个思维训练也挺有意思的
O(
【在 b********n 的大作中提到】
: 花了两个礼拜才做出来。。。各种查资料。。。
: 数学上面，得到恒定差的次数是p_1+...+p_n, 得到的定差结果是d1^p1*d2^p2...*dn^
: pn*(p1+..._pn)!
: 这个公式可以通过自己手推，把2个等差数列乘起来，你会发现求两次差就可以得到定
: 值，把3个乘起来，...一直到把n个乘起来，得到的求差次数是一个和式（在这个网页
: 里面有http://www.mymathforum.com/viewtopic.php?f=40&t=7993）而这个和式正好等于(p1+...+pn)!
: 下面的问题就在于提高运算效率，有三点
: 第一点就是如何maintain任何一个区间里的(p1+...+pn)和d1^p1*...*dn^pn. 这个因为
: 是range query，用segment tree得到，可以得到lg(n)的update和query time.如果每
: 次query都需要求一遍和的话，需要O(n)时间，如果提前算prefix sum的话，query是O(
|
