題目連結:
題目大意:
輸入有多列,每列給定兩正整數 x 、 n(1 ≦ x ≦ 10 ^ 6,1 ≦ n < 2 ^ 31),試問 1 + 2x + 3x ^ 2 + …… + (n + 1)x ^ n 之值為何?由於答案可能很大,所以請將答案模 10 ^ 9 + 7 後輸出。
範例輸入:
1 1
1 2
1 3
2 1
2 2
2 3
12345 123456
範例輸出:
3
6
10
5
17
49
480224489
解題思維:
因為
1 + x + x ^ 2 + …… + x ^ (n + 1)
對 x 微分後正好是題目的
1 + 2x + 3x ^ 2 + …… + (n + 1)x ^ n
而 1 + x + x ^ 2 + …… + x ^ (n + 1) 在前天的題目有提及過上式根據等比級數等價於
(x ^ (n + 2) - 1) ÷ (x - 1)
因此我們改微分
(x ^ (n + 2) - 1) ÷ (x - 1)
得
然後利用前天題目的策略便可以求得所求。不過同樣的,x = 1 時公式會出事,此時所求值 = (n + 2) × (n + 1) ÷ 2。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。