Установить биты в сочетании с экспоненциальной модульной арифметикой

Question

Я получил этот вопрос вчера в вызове. Я думал, что закодировал это правильно, и мой пример теста был пройден. Однако ни один тестовый пример не прошел на бэкэнде. Вот мой код Пожалуйста, кто-нибудь, помогите мне. Задача для меня окончена, и я не могу представить ее дальше. Но я хочу учиться на своих ошибках. Благодарю.

  import java.io.*;
//import java.util.*;


public class TestClass {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter wr = new PrintWriter(System.out);
         int n = Integer.parseInt(br.readLine().trim());
         String[] arr_a = br.readLine().split(" ");
         int[] a = new int[n];
         for(int i_a=0; i_a<arr_a.length; i_a++)
         {
            a[i_a] = Integer.parseInt(arr_a[i_a]);
         }

         long out_ = solve(a);
         System.out.println(out_);

         wr.close();
         br.close();
    }
    static long solve(int[] a){
        // Write your code here
        long sum = 0l;
        long MAX = 10000000011l;
        long i = 1l;
        for(int x : a) {
            long count = 0;
            while(x>0) {
                x &= (x-1l);
                count++;
            }
            long res = 1l;
            long temp = i;
            count = count % MAX;
            while(temp > 0) {
                if((temp & 1l) == 1l) {
                    res = (res * count) % MAX;
                }
                temp = temp >> 1l;
                count = ((count % MAX) * (count % MAX)) % MAX;

            }

            long t =((sum%MAX) + (res % MAX))%MAX;
            sum = t;
            i++;
        }

        return sum;
    }
}

Answer 1

Немного странно, что "даже ни один тестовый пример не пройден", но единственная ошибка, которую я вижу, это ваше возведение в квадрат по квадратуре.

Все ваши номера меньше 10^10 + 11, но эта константа имеет более 32 бит, и когда вы умножаете, вы иногда получаете переполнение (потому что long 64-разрядное целое число со знаком).

Это можно исправить несколькими подходами:

1. (a*b) % M Операция может быть выполнена с помощью алгоритма, аналогичного вашей реализации "возведение в квадрат". Вам просто нужно заменить все умножения на дополнения. В результате умножение заменяется на O(log(n)) операции сложения и умножения на 2. Пример реализации:

   static long multiply(long a, long b, long M) {
       long res = 0;
       long d = a % M;
   
       while (b > 0) {
           if ((b & 1) == 1) {
               res = (res + d) % M;
           }
   
           b >>= 1;
           d = (d + d) % M;
       }
       return res;
   }
   

2. Вы можете просто кешировать b^i % M числа для ранее вычисленных шагов. Для каждого количества установленных битов (их не так много) вы можете сохранить ранее вычисленные значения и last(b) - последний i когда a[i] имел b установить биты. Затем просто вычислите новое значение с помощью линейного цикла из last(b) + 1 до текущего индекса i,

3. Используйте BigInteger для умножения.