Для данного массива длины n найдите число подмножеств, где XOR подмножества равно заданному числу.

Question

Учитывая массив, arrдлины nнайти, сколько подмножеств arr есть такие, что XOR(^) из этих подмножеств равно заданному числу, ans,

у меня есть это dp подход, но есть ли способ улучшить его временную сложность. ans всегда меньше 1024.

Вот ans это нет. такой, что XOR(^) из подмножеств равно ему.arr[n] содержит все числа

memset(dp, 0, sizeof(dp));
dp[0][0] = 1;

for(i = 1; i <= n; i++){
    for(j = 0; j < 1024; j++) {
        dp[i][j] = (dp[i-1][j] + dp[i-1][j^arr[i]]);
    }
}

cout << (dp[n][ans]);

Answer 1

Из комментария user3386109, опираясь на ваш код:

/* Warning: Untested */
int counts[1024] = {0}, ways[1024];
for(int i = 1; i <= n; ++i) counts[ arr[i] ] += 1;
for(int i = 0; i <= 1024; ++i) {
  const int z = counts[i];
  // Look for overflow here
  ways[i] = z == 0 ?
              0 :
              (int)(1U << (z-1));
}

memset(dp, 0, sizeof(dp));
dp[0][0] = 1;

for(i = 1; i <= 1024; i++){
    for(j = 0; j < 1024; j++) {
        // Check for overflow
        const int howmany = ways[i] * dp[i-1][j];
        dp[i][j] += howmany;
        dp[i][j^i] += howmany;
    }
}

cout << (dp[1024][ans]);

Для расчета odd_ а также even_Вы также можете использовать следующее:

ⁿ c₀+ⁿ c₂+... = ⁿ c₁+ⁿ c₃... = 2^n-1

Потому что количество способов выбрать нечетные элементы = количество способов отклонить нечетные элементы = количество способов выбрать четные числа

Вы также можете оптимизировать пространство, сохранив только 2 столбца dp-массивов и используя их как dp[i-2][x] отбрасываются.

Answer 2

Идея, лежащая в основе динамического программирования, состоит в том, чтобы (1) никогда не вычислять один и тот же результат дважды и (2) вычислять только результаты по требованию, а не предварительно вычислять все, как вы это делаете.

Таким образом, есть решение, необходимое для solve(arr, n, ans) с ans < 1024, n < 1000000 а также arr = array[n], Идея иметь dp[n][ans] разумно указывать количество результатов, поэтому размер dp = array[n+1][1024], Нам нужен способ различать еще не вычисленные результаты и доступные результаты. Так memset(dp, -1, sizeof(dp)) а потом, как вы уже сделали dp[0][0] = 1

solve(arr, n, ans):
    if (dp[n][ans] == -1)
        if (n == 0) // and ans != 0 since that was initialized already
            dp[n][ans] = 0
        else
            // combine results with current and without current array element
            dp[n][ans] = solve(arr + 1, n - 1, ans) + solve(arr + 1, n - 1, ans XOR arr[0])
    return dp[n][ans]

Преимущество в том, что ваш dp Массив вычисляется только частично на пути к вашему решению, так что это может сэкономить некоторое время.

В зависимости от размера стека и nможет потребоваться перевести это из рекурсивного в итеративное решение