В этом задании вам дается нечетное количество белых шаров и столько же черных шаров. Задача состоит в том, чтобы подсчитать все способы помещения шаров в лотки так, чтобы в каждом лотке было нечетное число каждого цвета.

Например, скажем, у нас есть 3 белых шара. Различные способы:

(wwwbbb)
(wb)(wb)(wb)

для двух разных возможностей.

Если у нас есть 5 белых шаров, то есть разные способы:

(wwwwwbbbbb)
(wwwbbb)(wb)(wb)
(wwwb)(wbbb)(wb)
(wb)(wb)(wb)(wb)(wb)

Вы можете взять ввод, который представляет собой одно целое число, любым способом, который вам нравится. Выходные данные представляют собой одно целое число.

Ваш код должен быть достаточно быстрым, чтобы вы видели его завершенным для 11 белых шаров.

Вы можете использовать любой язык или библиотеку, которая вам нравится.

Par / GP, 81 байт

p=polcoeff;f(n)=p(p(prod(i=1,n,prod(j=1,n,1+(valuation(i/j,2)==0)*x^i*y^j)),n),n)

Для большей эффективности замените 1+на1+O(x^(n+1))+O(y^(n+1))+ (первый Oтермин уже очень помогает).

Попробуйте онлайн!(более ранняя 86-байтовая версия с парой ненужных паренов и без p=аббревиатуры)

Старая версия, 90 байт

f(n)=polcoeff(polcoeff(taylor(1/prod(i=0,n,prod(j=0,n,1-x^(2*i+1)*y^(2*j+1))),x,n+1),n),n)

Для вычислений f(11)требуется больший размер стека, в сообщении об ошибке будет указано, как его увеличить. Это более эффективно (но менее golfy) , чтобы заменить два , nкоторые появляются в качестве второго аргументов prodс (n-1)/2.

Python 3, 108 байт

C=lambda l,r,o=():((l,r)>=o)*l*r%2+sum(C(l-x,r-y,(x,y))for x in range(1,l,2)for y in range(1,r,2)if(x,y)>=o)

Рекурсивно перечисляет все наборы, стараясь не получать дубликаты, всегда генерируя наборы по порядку. Разумно быстро, когда запоминается с помощью C = functoools.lru_cache(None)(C), но это не обязательно для n = 11.

Позвоните, C(num_white, num_black)чтобы получить свой результат. Первая пара n:

1: 1
3: 2
5: 4
7: 12
9: 32
11: 85
13: 217
15: 539
17: 1316
19: 3146
21: 7374

Для генерации результатов:

def odd_parts(l, r, o=()):
    if l % 2 == r % 2 == 1 and (l, r) >= o:
        yield [(l, r)]

    for nl in range(1, l, 2):
        for nr in range(1, r, 2):
            if (nl, nr) < o: continue
            for t in odd_parts(l - nl, r - nr, (nl, nr)):
                yield [(nl, nr)] + t

Например, для (7, 7):

[(7, 7)]
[(1, 1), (1, 1), (5, 5)]
[(1, 1), (1, 1), (1, 1), (1, 1), (3, 3)]
[(1, 1), (1, 1), (1, 1), (1, 1), (1, 1), (1, 1), (1, 1)]
[(1, 1), (1, 1), (1, 1), (1, 3), (3, 1)]
[(1, 1), (1, 3), (5, 3)]
[(1, 1), (1, 5), (5, 1)]
[(1, 1), (3, 1), (3, 5)]
[(1, 1), (3, 3), (3, 3)]
[(1, 3), (1, 3), (5, 1)]
[(1, 3), (3, 1), (3, 3)]
[(1, 5), (3, 1), (3, 1)]

Python 3 , 180 172 байта

def f(n):
 r=range;N=n+1;a=[N*[0]for _ in r(N)];R=r(1,N,2);a[0][0]=1
 for i in R:
  for j in R:
   for k in r(N-i):
    for l in r(N-j):a[k+i][l+j]+=a[k][l]
 return a[n][n]

Попробуйте онлайн!

Простая реализация производящей функции. Долго, но (несколько) эффективно. O (n ⁴ ) время, O (n ² ) память.

Результирующий массив aсодержит все результаты всех размеров, вплоть до n, хотя a[n][n]возвращается только .

Python 2 ,168 181 байт

from itertools import*
r,p=range,product
def f(n):
 a,R=eval(`[[0]*n]*n`),r(1,n,2);a[0][0]=1
 for i,j in p(R,R):
  for k,l in p(r(n-i),r(n-j)):a[k+i][l+j]+=a[k][l]
 return a[-1][-1]

Попробуйте онлайн!

• Основано на ответе пользователя 202729 .
• Изменить: Сделано это независимая функция.
• Сохранено 2 байта благодаря пользователю 202729 .