c# - 在算法竞赛中不使用 BigInteger 库处理大整数

Question

问题:Topcoder SRM 170 500

考虑一个序列 {x0, x1, x2, ...}。根据先前项定义某个项 xn 的关系称为递归关系。线性递推关系是一种递推形式为 xn = 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 = 系数[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 modulo 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);
    }
}

此解决方案的问题是 double 表示的精度，并且由于我无法使用第三方库或 .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 - 失败返回 8由于 double 类型的精度，为 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 .

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