Матричная задача в C

Question

В матрице mxn, имеющей k объектов, каково количество способов помещения объекта в ячейку матрицы (k <= n, m).Приведя пример, который будет лучше проиллюстрирован, если 1-й объект из «k» объектов был размещен в местоположении (1,1), то следующий объект не может быть размещен в 1-м столбце или в 1-й строке и надля остальных оставшихся объектов. </p>

Вывод задачи будет выглядеть следующим образом: (k-й объект, n-я строка, m-й столбец), т. е. (3,3,4) или неформально: «Сколько способов можнообъекты должны быть размещены в (nxm) ячейках матрицы.

Я узнал рабочее правило, скажем: [n (n-1) (n-2) ... (n- (k-1))][m (m-1) (m-2) ... (m- (k-1))] -> это даст мне точное количество способов, k объектов могут быть помещены в ячейку, с примененнымограничения.

Но я не могу сконструировать условие «вложенный цикл»: for (объект) for (строка) for (столбец)

Я ИСПОЛЬЗУЮ C!

нужна помощь в создании кода!

Answer 1

Как я уже сказал здесь , просто реализуйте это .

/* n,m,k are constants */
int rook() {
    int i, j, mem[m+1][k+1];
    for (i=0; i<=m; i++)
        mem[i][0] = 1;
    for (j=1; j<=k; j++)
        mem[0][j] = 0;
    for (i=1; i<=m; i++)
        for (j=1; j<=k; j++)
            mem[i][j] = mem[i-1][j] + (n-j+1)*mem[i-1][j-1];
    return mem[m][k];
}

Как обычно, вы можете оптимизировать это для использования O (k) пробела.

Answer 2

Посмотрите вверх Полиномы грача