Допустим, есть какое-то число m=260,
которое нужно разложить на n=8 разных слагаемых
(одинаковые слагаемые не допускаются), каждое
из которых не превосходит s=n^2=64 (лежат в диапазоне от 1 до 64).

Как найти количество разбиений числа m на n таких слагаемых в общем виде?

m=n*(n^2+1)/2=260 при n=8

конечно брутфорс есть алгоритм (и не один),
но хотелось бы что-нибудь получше
поскольку на таких числах временные затраты велики

>  временные затраты велики

ну и что? просчитай заранее, занеси в таблицу. исходя из "лежат в диапазоне от 1 до 64"
это ряд чисел m от 36 до 484, что не так уж много.

Я только за деньги готов - вспоминать надо

> Я только за деньги готов - вспоминать надо

да брутфорс там вообще примитивный
например,

> исходя из "лежат в диапазоне от 1 до 64"

n тоже переменная и n^2 может быть значительно больше 64, поэтому
я думаю нет смысл заранее рассчитывать - ресурсов не хватит...

> Sha ©   (23.06.18 16:31) [7]

а как вывести получившееся суммы?
чего-то больно много получается

Как вывести, не знаю.
Не думаю, что получится простая формула.

Так считает немного быстрее за счет исключения последнего цикла:
function xayam2(Max, Sum, Count: integer): integer;
var
 i: integer;
begin;
 Result:=0;
 if Count>1 then begin;
   if Max>Sum then Max:=Sum;
   for i:=Max downto 1 do Result:=Result + xayam2(i-1, Sum-i, Count-1);
   end
 else if (Count=1) and (0<Sum) and (Sum<=Max) then Result:=1;
 end;


> Sha ©   (23.06.18 17:30) [9]
> Как вывести, не знаю.
> Не думаю, что получится простая формула.

самое интересное что эта задача прямо соотносится с задачей о расстановки ферзей.
И связано с магической константой квадрата.
Вот накатал пример
https://ic.pics.livejournal.com/xayam/26173943/38977/38977_900.png

там опечатка в координатах, но смысл тот же - сумма координат ферзей дает магическую константу (что легко выводится формульно), однако наоборот неверно - если разложить магическую константу на n слагаемых - это не значит что получившиеся координаты будут координатами не угрожающих друг другу ферзей - необходимо еще вычесть количество диагональных коллизий...

> Sha ©   (23.06.18 17:30) [9]

причем основная проблема этих чертовых ферзей - это как раз диагональные коллизии
Как думаешь их кол-во реально посчитать без генерации самих координат?

Все давно посчитано.
Перебором )

> Sha ©   (23.06.18 18:07) [13]
> Все давно посчитано.
> Перебором )

до n=27 а дальше тупик
https://oeis.org/search?q=A000170

Еще немного быстрее (1.25 сек на i7-7700)
function xayam3(Max, Sum, Count: integer): integer;
begin;
 Result:=0;
 if Count<=1 then begin;
   if (0<Sum) and (Sum<=Max) then Result:=1;
   end
 else begin;
   if Max>Sum then Max:=Sum;
   while Max>=Count do begin;
     Result:=Result + xayam3(Max-1, Sum-Max, Count-1);
     dec(Max);
     end;
   end;
 end;


чего-то больно большие числа выдает алгоритм.
Мне кажется он не учитывает что числа разложения должны быть разными.
Может переформулировать задачу.
Например, сколько определителей равных единице существует для матрицы размером n x n.
Сами элементы матрицы равны или 0 или 1.
Местоположение 1 определяет координаты ферзя на доске.
Соответственно единиц ровно n штук в матрице.
И судя по определению, неединичные определители могут возникать только если в столбце и/или в строке более одной единицы.

вообще по идее таких определителей должно быть n! (n факториал).

> Sha

или нет?

> И судя по определению, неединичные определители могут возникать
> только если в столбце и/или в строке более одной единицы.

а так как количество единиц ограничено то получается
тогда существует строка или столбец где все элементы нулевые -
значит и определитель равен нулю

хотя возможно определитель еще может быть равен -1
тогда всех определителей равных -1 и 1 ровно n! а сколько равных только единице непонятно.

???

> а сколько равных только единице непонятно

хотя по идее почти все симметрично и их ровно n!/2-1
минус один так как единичная матрица (все единицы на диагоналях) не имеет симметричного представления

> хотя по идее почти все симметрично и их ровно n!/2-1

опс точнее (n!-1)/2
но это только если n нечетно.
Если же n четно то непонятно.

>xayam ©   (01.07.18 06:50) [16]
>чего-то больно большие числа выдает алгоритм.

Функция имеет параметры.
Что мешает проверить ее работу для небольших значений параметров,
когда можно вычислить правильный результат на бумажке и сравнить?

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

Можно все это проделать намного быстрее, если отказаться от рекурсии:
function xayam5(Max, Sum, Count: integer): integer;
var
 a, b: array of array of integer;
 p: pointer;
 m, s, k, i, v: integer;
begin;
 Result:=0;
 if (Count<=0) or (Sum<=0) or (Max<=0) then exit;

 if Max>Sum then Max:=Sum;
 SetLength(a,1+Sum,1+Max);
 SetLength(b,1+Sum,1+Max);
 for s:=0 to Sum do for m:=0 to Max do b[s,m]:=0;
 for m:=1 to Max do b[m, m]:=1;
 for k:=2 to Count do begin;
   p:=pointer(a); pointer(a):=pointer(b); pointer(b):=p;
   for s:=0 to Sum do for m:=0 to Max do b[s,m]:=0;
   for s:=k to Sum do begin;
     i:=s; if i>Max then i:=Max;
     for m:=1 to i do begin;
       v:=0;
       for i:=1 to m-1 do v:=v+a[s-m,i];
       b[s,m]:=v;
       end;
     end;
   end;

 for i:=1 to Max do Result:=Result+b[Sum, i];
 end;


Можно все это проделать до запредельных значений,
если поменять тип результата на int64.

Было бы желание.

Кешировать надо, у вас много повторений (ИМХО). Например, если рассмотреть 64, 61, а потом 63, 62, то при Max <= 60 у нас будут абсолютно идентичное количество, которое вы честно будете считать два раза. Так что лучше иметь массив 260x64x8, куда записывать уже вычисленные результаты (133k элементов).

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

> Mystic ©   (03.07.18 09:20) [23]

... а вот это попробуйте )

Попробовал сильно не вникая в оптимизацию

Угадал с ответом?

> Mystic ©   (03.07.18 13:08) [26]
> Угадал с ответом?

Да, ответ верный и время совпадает.

Чтобы заметить разницу в скорости потребуется увеличить размерность задачи,
но тогда упремся в оперативную память и ограничения компилятора.

А почему время совпадает?


> Еще немного быстрее (1.25 сек на i7-7700)


У меня же получилось 0.001 секунды, при том, что

У меня такое чувство, что мы скорее упрёмся в производительность процессора, чем в память.

У моём примере используется 1085760 byte памяти (мегабайт).

Если увеличить все параметры в пять раз, а max в 50, мы получим




Т. е. надо около гигабайта памяти и почти переполнение типа uint64_t (30% от MAX_UINT64).

> Mystic ©   (03.07.18 16:37) [29]
> А почему время совпадает?

Это [15], которая с рекурсией, работает больше секунды.
А время [22], которая без рекурсии, тоже 0 ms.

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

> Mystic ©   (03.07.18 16:50) [30]
> Если увеличить все параметры в пять раз, а max в 50, мы получим

При таких размерах кеш сумм будет очень полезен.

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