java - 不使用大整数的大幂

Question

我遇到了一个问题，我必须计算数组中数字的大幂的总和并返回结果。例如 arr=[10,12,34,56] 那么输出应该是10^1+12^2+34^3+56^4。这里的输出可能非常大，所以我们被要求对输出取 10^10+11 的模，然后返回它。我在 python 中很容易做到，但在 java 中最初我使用 BigInteger 并得到了一半的测试用例，所以我想到使用 Long，然后使用模指数计算功率，但后来我得到了错误的输出，全部精确为负数，因为它显然超出了限制。

这是我使用长指数和模指数的代码。

static long power(long x, long y, long p)
{
    long res = 1;      // Initialize result

    x = x % p;  // Update x if it is more than or 
                // equal to p

    while (y > 0)
    {
        // If y is odd, multiply x with result
        if ((y & 1)==1)
            res = (res*x) % p;

        // y must be even now
        y = y>>1; // y = y/2
        x = (x*x) % p;  
    }
    return res;
}

static long solve(int[] a) {
    // Write your code here
    Long[] arr = new Long[a.length];

    for (int i = 0; i < a.length; i++) {
        arr[i] = setBits(new Long(a[i]));
    }
    Long Mod = new Long("10000000011");
    Long c = new Long(0);
    for (int i = 0; i < arr.length; i++) {
        c += power(arr[i], new Long(i + 1),Mod) % Mod;
    }

    return c % Mod;
}

static long setBits(Long a) {
    Long count = new Long(0);
    while (a > 0) {
        a &= (a - 1);
        count++;
    }
    return count;
}

然后我也尝试了二进制指数，但对我来说没有任何作用。我如何在不使用大整数的情况下实现这一点，并且像我在 python 中得到的那样简单

Answer 1

您为 mod 的值添加了一个额外的零，它应该是 1000000011。希望这能解决这个问题