查找系列的第X項

Question

我有一個簡單的問題。

我有一個N數組的數組A []。我必須執行這個操作：

for(i = 2; i<=N; i++) 
    A[i] = A[i] + A[i-1] 

到數組A [] k次。執行此操作k次後，必須輸出第X個索引元素。

用蠻力做這件事，會導致TLE。

我正在尋找某種模式，但是，我找到了一個並不完美的解決方案，因爲它需要。

您能否幫我解決一下這個問題？

我有一個例子，要清除這個問題。

假設數組A是[1,2,3]，我需要執行上述操作3次，然後：

後第一個轉彎

陣：A=[1,3,6]後第二次轉
陣：A=[1,4,10]後第3轉
陣：A=[1,5,15]

因此，如果我需要現在查找數組的第二個元素，那麼它將是5.

Answer 1

我看你的帕斯卡三角形（如@MBo所說），您可能會注意到，在k次之後，每個數字在最終結果中添加的次數等於對角線之後的三角形中的平方。讓我們在這裏看到一個例子：

該圖像對應重複四次，前三個元素。因此，您可以看到，如果我們輸入的k等於次數並且n等於要返回的元素的索引，我們所要做的就是將填充爲藍色的對角線中的每個數字相乘，直到紅色線（圖像配置對應於k = 4和n = 2）。

之後，我們有這樣的公式：

現在，以提高我們計算上面的公式顯示的方式，我們可以使用動態編程和從0計算階乘函數...，K + n（注意序列中較大的數字是k-1 + n）。有了這個，我們可以在一段時間內訪問factorial(n)。同樣，如果我們擴大總和內的組合因子，我們注意到因子(k - 1 + i - i)! = (k - 1)!因此，我們可以將其放在總和之外。

下面是代碼：

#include "stdafx.h" 
#include "iostream" 

using namespace std; 

int findingXth(int a[], int n, int k, int factorial[]){ 

    if (k == 0) 
     return a[n]; 

    int result = 0; 

    for (int i = 0; i <= n; ++i) 
    { 
     int up = k - 1 + i; 
     result += (factorial[up]/factorial[i]) * a[n - i]; 
    } 
    return result/factorial[k - 1]; 
} 

int main(int argc, _TCHAR* argv[]) 
{ 
    int a[3] = { 1, 2, 3 }; 
    int n = 2; 
    int k = 3; 

    int factorial[100000]; // probably the expecification of the problem has some upper bounds for n and k (the length of the factorial array can be set to n+k+1); 
    factorial[0] = 1; 

    for (int i = 1; i < n + k; i++) 
    { 
     factorial[i] = factorial[i - 1] * i; 
    } 

    int result = findingXth(a, n, k, factorial); 

    std::cout << result; 

    return 0; 
}