Как я могу найти общее количество различных массивов, которые могут быть получены после применения данной операции ровно в k раз?

Question

Учитывая, что массив и элементы внутри массива находятся в диапазоне [-10^6, 10^6]. У нас также есть целое число k, и нам нужно найти, сколько различных массивов можно получить, применяя операцию точно k раз. Единственная операция - выбрать любой элемент массива и умножить его на -1.

Например, массив A = {1, 2, 1} и k = 2, различные массив, полученный после k операций 4 ({1, 2, 1}, {-1, -2, 1}, {-1, 2, -1}, {1, -2,-1}).

Хотя код и объяснение предоставляются here, но это трудно понять. Пожалуйста, кто-то упростить это объяснение или дать какой-то другой подход для решения проблемы.

Answer 1

Пусть размер массива равен n. Сначала убедитесь, что ответ не зависит от порядка выполненных операций.

Рассмотрим два случая:

Case 1: Там нет нулей в массиве и

Случай 2: Есть ненулевое число нулей в массиве.

Учитывая Случай 1:

Sub-Case 1: Количество элементов> = количество операций, т.е. п> к

Предположим, что мы допускаем максимум 1 операции по каждый элемент, мы можем видеть, что мы можем получить ⁿ c _k различные массивы, имеющие k измененные элементы оригинала массив.

Но что происходит, когда мы выполняем 2 операции над одним элементом? Элемент в принципе не изменяется и имеет в виду, что порядок операций не изменяется, вы можете сказать так: вы взяли начальный массив, выбрали элемент, умножили его на -1 дважды, и, следовательно, вы с точный исходный массив теперь, но только с k-2 операций в вашей руке, что означает, что мы выбрасываем 2 из наших шансов. Теперь мы можем тщательно выполнить операции k-2 по одному на каждом элементе и получить ⁿ c _k-2 различные массивы. Точно так же вы можете выбросить 4, 6, 8, .... шансы и получить ^п с _к-4, ^п с _K-6^{, п} с _к-8, .. ... массивов соответственно для каждого случая.

Это приводит к ^п с _к + ^п с _к-2 + ^п с _к-4 + ^п с _к-6 + ^п с _k-8 + ....... количество возможных массивов, если ни один элемент в массиве не равен нулю.

Sub Case 2: п < к

Поскольку число операций больше, чем число элементов, которые вы должны выбросить некоторые из ваших операций, потому что вы должны применять более 1 операцию в хотя бы один элемент. Итак, если n и k оба четные или оба нечетные, вы должны выбросить kn ваших операций и уйти n операций, а отсюда это будет только случайный случай 1. Если один нечетный, а один даже вам нужно выбросить k -n + 1 ваших операций и у вас осталось n-1 операций, и снова это будет только пример 1 с этой точки. Вы можете попытаться получить выражение для этого случая.

Учитывая случай 2:

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

Даже здесь, возникают случаи п> = к и п < к.

Для п> = к случай:

Поскольку существует по крайней мере один нуль, теперь вы сможете выбросить любое количество операций, просто применяя, что число операций на любом из нулей, так как умножение нуля на -1 не влияет на него.

Так что ответ здесь будет просто ^п с _к + ^п с _к-1 + ^п с _к-2 + ^п с _к-3 + ^п с _к-4 + .......

А для п < к случай:

Ответ будет ^п с _п + ^п с _п-1 + ^п с _п-2 + ^п с _п-3 + ⁿ c _n-4 + .......= 2 ^п

Я думаю, что это динамическая задача программирования, потому что вы должны вычислить сумму ^п с _г с. Логика - это комбинаторная задача.

Answer 2

Ok давайте Повсеместно код,
Сначала эта функция nChoosek: это функция, вычислить комбинацию калькулятор, и это то, что будет использоваться для решения проблемы
Conbinaison в основном количество выбора часть коллекции https://en.wikipedia.org/wiki/Combination
Пример массива {1, 2, 3}, если я скажу, что вы выбрали два элемента из трех элементов массива, это комбинация буксировки из трех, в коде это nChoosek (2,3) = card {(1,2), (2,3), (1,3)} = 3
Если мы рассмотрим проблему с этими тремя дополнительными условиями
1- вы не можете умножить один и тот же элемент дважды
2- п < = к
3- нет нуля в массиве
Решения здесь будет nChoosek (к, п), но так как эти ограничения существуют мы имеем дело с каждым из них
Для самых сначала мы можем умножить один и тот же элемент дважды: так что для nChoosek (k, n) нам нужно количество массива, которое мы можем получить, если умножить элемент (или много) на два на -1 .. , но подождите, давайте рассмотрим комбинацию когда мы умножаем один элемент дважды: здесь мы потеряли два умножения без изменения массива, поэтому количество комбинаций, которое у нас есть, будет nChoosek (k -2, n)
Точно так же, если мы решили умножить два элемента в два раза на результат будет nChoosek (k -4, n)
Отсюда происходит

for(; i >= 0; i -= 2){ 
     ans += nChoosek(n, i); 
     ans = ans % (1000000007l); 

    } 

Для случая, когда к> п применения алгоритма означает, что мы будем умножать по крайней мере один элемент в два раза, так что похоже на применение нового алгоритма с к-2 и п
, если k- 2 еще больше, чем n, мы можем по той же логике преобразовать его в эквивалент с n и k-4 и так далее, пока k-2 * i < = n и k-2 * (i + 1)> 0
Очевидно вот что это к-2 * я будет п или п-1, так что новый будет к п или п-1, и это оправдывает этот код

if(k <= n){ 
     i = k; 
    }else if((k % 2 == 0 && n % 2 == 0) || (k % 2 != 0 && n % 2 != 0)){ 
     i = n; 
    }else if((k % 2 == 0 && n % 2 != 0) || (k % 2 != 0 && n % 2 == 0)){ 
     i = n - 1; 
    } 

Теперь история нуля, если мы рассмотрим T1 = {1,2,3} и T2 = {0,1,0,0,2,3,0,0,0} и k = 2, вы можете заметить, что дело с массивом с длиной = n и имеет m нуль, похоже на дело с массивом длины = nm без нуля