在算法竞赛中处理没有BigInteger库的大整数

Question

问题: Topcoder SRM 170 500

考虑序列{x0，x1，x2，.}。用前一项定义某项xn的关系称为递推关系。线性递推关系的形式是:x= c( k -1) * x(n-1) + c(k-2) * x(n-2) +.+ c(0) * x(n-k)，其中所有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 =系数xn 1* xn-1 +系数xn 2* xn-2 +.+系数*xn。

例如，如果系数= {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);
    }
}

这个解决方案的问题是双重表示的精确性，而且由于我不能为这个SRM使用第三方库或BigInteger库，所以我需要找到一种没有它们的方法来解决它。我怀疑我可以使用递归，但我对如何解决这个问题有点一无所知。

下面是一个测试用例，它显示了我的代码何时工作，何时不起作用

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

有人能帮我弄清楚吗？我本来打算用数组来存储这些值，但这有点超出了我的范围，特别是关于如何处理乘法，并且仍然在问题中所规定的时间和空间复杂度之内。也许我的整个方法都错了？我希望有一些指点和指导(没有充分充实的答案)，请回答。

谢谢

Answer 1

注意，我们只需要返回xn的模块10。

我们还需要知道如果a = b + c，我们有a % 10 = (b % 10 + c % 10) %10.

和a = b*c，所以我们也有a % 10 = (b %10 * c % 10) % 10;

所以，为了

xn = c(k-1) * x(n-1) + c(k-2) * x(n-2) + ... + c(0) * x(n-k) 
            = a0 + a1 + .... + an 

( a0 =c(k-1)*x(n-1)，a1 =.)

我们有xn % 10 = (a0 % 10 + a1 % 10 + ...)%10

对于每一个ai = ci*xi，所以ai % 10 = (ci % 10 * xi % 10)% 10。

因此，通过做所有这些数学计算，我们可以避免使用双倍，并将结果保持在可管理的大小。

Answer 2

正如Pham所回答的，诀窍是认识到您只需要返回一个模块，从而绕过溢出问题。这是我的快速尝试。我使用一个队列将最后一个结果xN放入其中，并将最老的队列排除在外。

    static int solve(int[] coefficients, int[] seed, int n)
    {
        int k = coefficients.Count();
        var queue = new Queue<int>(seed.Reverse().Take(k).Reverse());

        for (int i = k; i <= n; i++)
        {

            var xn = coefficients.Zip(queue, (x, y) => x * y % 10).Sum() % 10;
            queue.Enqueue(xn);
            queue.Dequeue();
        }

        return (int) (queue.Last() );

    }

编辑:获得与您预期的结果相同的结果，但是我并不保证在这个示例中没有错误。