我怎样才能找到恰好应用给定操作 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。首先看到答案不依赖于完成的操作顺序。

考虑两种情况：

情况 1 :数组中没有零并且

情况 2：数组中有非零个数的零。

考虑案例 1：

Sub-Case 1 : Number of elements >= number of operations i.e n > k

Suppose we allow a maximum of 1 operation on every element, we can see that we can get ⁿc_k different arrays having k changed elements from the original array.

But what happens when we do 2 operations on a single element ? The element basically doesn't change and keeping in mind that the order of operations doesn't change, you can put it this way : You took the initial array, selected an element, multiplied it by -1 twice and hence you are with the exact original array now but with just k-2 operations in your hand which means that we are throwing away 2 of our k chances initially. Now we can carefully perform the k-2 operations one on each element and get ⁿc_k-2 different arrays. Similarly you can throw away 4, 6, 8, .... chances and get ⁿc_k-4, ⁿc_k-6, ⁿc_k-8, ..... arrays respectively for each case.

This leads to ⁿc_k+ⁿc_k-2+ⁿc_k-4+ⁿc_k-6+ ⁿc_k-8+ ....... number of possible arrays if no element in the array is zero.

Sub Case 2 : n < k

Since the number of operations are greater than number of elements you have to throw away some of your operations because you have to apply more than 1 operation on at least one element. So, if n and k both are even or both are odd you should throw k-n of your operations and have n operations left and from here it is just the sub case 1. If one is odd and one is even you have to throw away k-n+1 of your operations and have n-1 operations left and again it is just the sub case 1 from this point. You can try to get the expression for this case.

考虑 案例 2：

Notice that in the earlier case you were only able to throw away an even number of operations.

Even here, there arise the cases n >= k and n < k.

For n >= k case :

Since there is at least one zero, you will now be able to throw away any number of operations by just applying that number of operations on any of the zeros since multiplying a zero with -1 doesn't affect it.

So the answer here will simply be ⁿc_k+ⁿc_k-1+ⁿc_k-2+ⁿc_k-3+ ⁿc_k-4+ .......

And for n < k case :

The answer would be ⁿc_n+ⁿc_n-1+ⁿc_n-2+ⁿc_n-3+ ⁿc_n-4+ ....... = 2ⁿ

我认为这是一个动态规划问题，因为你必须计算ⁿc_rs的总和。逻辑上这是一个组合问题。

Answer 2

好的，让我们看一下代码，
首先是nChoosek这个函数：它是一个计算组合计算器的函数，这就是用来解决问题的
Conbinaison 基本上是选择集合的一部分的数量 https://en.wikipedia.org/wiki/Combination
数组 {1, 2, 3} 的示例，如果我告诉你从数组的三个项目中选择两个项目，这是拖车的组合从三个，在代码中是 nChoosek(2,3) = card{(1,2), (2,3), (1,3)} = 3
如果我们考虑这三个附加条件的问题
1- 你不能将同一个项目乘以两次
2- n<=k
3- 数组中没有零
这里的解决方案是 nChoosek(k,n) 但由于存在这些限制，我们必须处理每个限制
对于第一个，我们可以将相同的项目乘以两次：因此对于 nChoosek(k,n) 我们应该将一个项目（或多个项目）乘以 -1 两次时我们可以拥有的数组数量。但是等一下，让我们考虑一下当我们将单个项目乘以两次时的组合：这里我们在不更改数组的情况下丢失了两次乘法，因此我们拥有的组合数将为 nChoosek(k -2 ,n)
同样，如果我们决定将两个项目相乘两次，结果将是 nChoosek(k -4 ,n)
由此而来

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

    }

对于 k > n 应用算法的情况意味着我们将至少将一个元素乘以两次，因此它类似于应用 k-2 和 n 的算法
如果 k-2 仍然大于 n 我们可以通过相同的逻辑将其转换为 n 和 k-4 等价物，依此类推直到 k-2*i <=n and k- 2 *(i+1) > 0
这里很明显，这个 k-2*i 将是 n 或 n-1，所以新的 k 将是 n 或 n-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 为零的数组类似于处理长度 = n-m 且不为零的数组

我怎样才能找到恰好应用给定操作 k 次后可以获得的不同数组的总数？

How can i find the total number of distinct arrays that can be obtained after applying given operation exactly k times?

algorithm

dynamic-programming

combinatorics