I am working on a problem which I believe I have reduced to the following. I know that there's a better solution to this problem but I wanted to see if there's any interesting solution to find in this direction.
I have the following matrix
A =
[
1 1 1 1 1 ...
1 2 3 4 5 ...
1 3 6 10 15 ...
1 4 10 20 35 ...
1 5 15 35 70 ...
...
]
Notice that A[i][j] = A[i-1][j] + A[i][j-1]
and that the diagonals form binomial coefficient patterns.
I want to evaluate the following function in better than O(n) time.
f(i,n,x) = (A[i][0] * x + A[i][1] * x^2 + A[i][2] * x^3 + ... + A[i][n] * x^n) % bigPrime
If it helps, there are a fixed, very small, number of values of x for which I will ever need to evaluate this at.
For example, say x is only ever in {1, 2, 3}.
Is this possible?