在算法竞赛中无需BigInteger库即可处理大整数

问题：Topcoder SRM 170 500

考虑序列{x0，x1，x2，...}。根据先前项定义某些项xn的关系称为递归关系。线性递归关系是递归形式为xn = c（k-1）* x（n-1）+ c（k-2）* x（n-2）+ ... + c（0 ）* x（nk），其中所有c（i）都是实数值常量，k是递归关系的长度，n是大于或等于k的任意正整数。您将得到一个int []系数，依次表示c（0），c（1），...，c（k-1）。您还将获得一个int []初始值，给出x（0），x（1），...，x（k-1）和一个int N的值。您的方法应返回xN以10为模。

更具体地说，如果系数的大小为k，则递归关系将为xn =系数[k-1] * xn-1 +系数[k-2] * xn-2 + ... +系数[0] * xn -k。

例如，如果系数= {2,1}，初始= {9,7}，并且N = 6，则我们的递归关系为xn = xn-1 + 2 * xn-2，则x0 = 9且x1 = 7.然后x2 = x1 + 2 * x0 = 7 + 2 * 9 = 25，类似地，x3 = 39，x4 = 89，x5 = 167和x6 = 345，因此您的方法将返回（345模10）= 5，

约束：-代码运行时间必须少于或等于2秒-内存使用率不得超过64 MB

我尝试的解决方案：

class RecurrenceRelation
{

    public int moduloTen(int[] coefficients, int[] initial, int N)
    {
        double xn = 0; int j = 0;
        int K = coefficients.Length;
        List<double> xs = new List<double>(Array.ConvertAll<int, double>(initial,
        delegate(int i)
        {
            return (double)i;
        })); 
        if (N < K)
            return negativePositiveMod(xs[N]);
        while (xs.Count <= N)
        {
            for (int i = xs.Count - 1; i >= j; i--)
            {
                xn += xs[i] * coefficients[K--];
            }
            K = coefficients.Length;
            xs.Add(xn);
            xn = 0;
            j++;
        }
        return negativePositiveMod(xs[N]);
    }
    public int negativePositiveMod(double b)
    {
        while (b < 0)
        {
            b += 10;
        }
        return (int)(b % 10);
    }
}

这个解决方案的我的问题是双重表示的精度，并且由于我无法将第三方库或.NET中的BigInteger库用于此SRM，因此我需要找到一种在没有它们的情况下解决它的方法。我怀疑我可以使用递归，但是我对此一无所知。

这是一个测试用例，显示我的代码何时起作用，何时不起作用

{2,1}，{9,7}，6-成功返回5 {9,8,7,6,5,4,3,2,1,0}，{1,2,3,4,5， 6,7,8,9,10}，654-由于double类型的精度而未成功返回8而不是5

谁能帮我解决这个问题？我本来打算使用数组来存储值，但是这超出了我一点，特别是在如何满足乘法方面，并且仍然处于问题中所指出的时间和空间复杂度之内。也许我的整个方法是错误的？我希望能得到一些指示和方向（未完全充实答案）。

谢谢