Сумма пар чисел с исключающим ИЛИ

Question

Stopwatch stopwatch = new Stopwatch();
Console.Write("Введите число n: ");
int n = int.Parse(Console.ReadLine());
double sum = 0;
double mod = Math.Pow(10,9) + 7;
stopwatch.Start();
 
for (int i = 1; i <= n; i++)
{
   for (int j = i + 1; j <= n; j++)
   {
      sum += (i^j);
      //sum %= mod;
   }
}
 
stopwatch.Stop();
Console.WriteLine("Время выполнения: " + stopwatch.ElapsedMilliseconds + " мс");
Console.WriteLine(sum);
Console.ReadKey();

Нужно чтобы время выполнения было не больше секунды.

Задача: Помогите Тане! Посчитайте сумму по всем парам ее мячей исключающих или их номеров. Таня не любит большие числа, так что ответ необходимо вывести по модулю 109 + 7. Например, если у Тани было 3 мяча, то искомое значение равно (1 ⊕ 2) + (1 ⊕ 3) + (2 ⊕ 3) = 3 + 2 + 1 = 6.

Ввод: 33328 Вывод: 866456930

Answer 1

От чего зависит значение суммы? От того, как будут складываться биты, стоящие на каждой позиции.

Если рассмотреть k-й бит, то из всех возможных пар чисел единицы на этой позиции дадут пары, в которых у одного числа этот бит нулевой, а другой единичный.

Значит, можно пройти по всем числам и подсчитать количество тех, в которых этот бит установлен One[k], и тех, у которых сброшен Zero[k].

В результате получится One[k]*Zero[k] пар, столько же единичек в k-ом бите войдёт в общую сумму, и их вклад в общую сумму будет One[k]*Zero[k] * (1<<k).

Остается сделать это для всех возможных номеров битов (надо полагать, не более 32)

Получается линейная сложность от n. Если ограничения невелики, этого за глаза хватит.
А вообще можно за логарифм битики посчитать, воспользовавшись тем, что в диапазоне 0..2^m-1 каждый бит установлен в половине чисел (2^(m-1))

БЛОГ НА HUSL

Сумма пар чисел с исключающим ИЛИ

Ответы (1 шт):