34) Ожерелья
Задача "ожерелья" — это одна из классических комбинаторных задач. Требуется посчитать количество различных ожерелий из бусинок, каждая из которых может быть покрашена в один из цветов. При сравнении двух ожерелий их можно поворачивать, но не переворачивать (т.е. разрешается сделать циклический сдвиг).
Решение
Решить эту задачу можно, используя лемму Бернсайда и теорему Пойа. [ Ниже идёт копия текста из этой статьи ]
В этой задаче мы можем сразу найти группу инвариантных перестановок. Очевидно, она будет состоять из перестановок:
Найдём
явную формулу для вычисления 
.
Во-первых, заметим, что перестановки
имеют такой вид, что в
-ой
перестановке на
-ой
позиции стоит 
(взятое
по модулю
,
если оно больше
).
Если мы будем рассматривать циклическую
структуру
-ой
перестановки, то увидим, что единица
переходит в 
,
переходит
в 
,
—
в 
,
и т.д., пока не придём в число 
;
для остальных элементов выполняются
похожие утверждения. Отсюда можно
понять, что все циклы имеют одинаковую
длину, равную 
,
т.е. 
("gcd"
— наибольший общий делитель, "lcm"
— наименьшее общее кратное). Тогда
количество циклов в
-ой
перестановке будет равно просто 
.
Подставляя найденные значения в теорему Пойа, получаем решение:
Можно
оставить формулу в таком виде, а можно
её свернуть ещё больше. Перейдём от
суммы по всем
к
сумме только по делителям
.
Действительно, в нашей сумме будет много
одинаковых слагаемых: если
не
является делителем
,
то таковой делитель найдётся после
вычисления
.
Следовательно, для каждого делителя 
его
слагаемое 
учтётся
несколько раз, т.е. сумму можно представить
в таком виде:
где 
—
это количество таких чисел
,
что 
.
Найдём явное выражение для этого
количества. Любое такое число
имеет
вид: 
,
где 
(иначе
было бы 
).
Вспоминая функцию
Эйлера, мы находим, что
количество таких
—
это величина функции Эйлера 
.
Таким образом, 
,
и окончательно получаем формулу:
35)Задача о ферзях
int SIZE = 0;
int board[13][13];
int results_count = 0;
void showBoard()
{
for(int a = 0; a < SIZE; ++a)
{
for(int b = 0; b < SIZE; ++b)
{
std::cout << ((board[a][b]) ? "Q " : ". ");
}
std::cout << '\n';
}
}
bool tryQueen(int a, int b)
{
for(int i = 0; i < a; ++i)
{
if(board[i][b])
{
return false;
}
}
for(int i = 1; i <= a && b-i >= 0; ++i)
{
if(board[a-i][b-i])
{
return false;
}
}
for(int i = 1; i <= a && b+i < SIZE; i++)
{
if(board[a-i][b+i])
{
return false;
}
}
return true;
}
void setQueen(int a) {
if(a == SIZE)
{
results_count++;
return;
}
for(int i = 0; i < SIZE; ++i)
{ if(tryQueen(a, i))
{
board[a][i] = 1;
setQueen(a+1);
board[a][i] = 0;
}
}
return;
}
int main()
{
std::cin >> SIZE;
setQueen(0);
std::cout << results_count << std::endl;
return 0;
}