2008,
TCHS, Весна, Раунд 1, День декораций (DecorationDay)
Двое играют в следующую игру.
Первый игрок разложил несколько кучек монет перед вторым и просит его выбрать
одну или несколько групп монет. При этом НОД (наибольший общий делитель)
количества монет в выбранных группах должен равняться 1. Например, из кучек {2,
3, 4} можно выбрать {2, 3} или {2, 3, 4}, но никак не {2, 4}.
Массив groups
описывает количество монет в кучках. Необходимо определить количество способов,
которыми второй игрок может сделать выбор кучек.
Класс: DecorationDay
Метод: int howMany(vector<int> groups)
Ограничения:
groups содержит от 1 до 50 элементов, 1 £ groups[i]
£ 100000.
Вход. Массив groups, описывающий количество
монет в кучках.
Выход. Количество способов, которыми
второй игрок может сделать выбор кучек.
Пример входа
|
groups |
|
{2, 4, 3} |
|
{2, 2, 2, 4} |
|
{2, 2, 3} |
|
{2, 5, 98872, 23298, 32872, 23111} |
|
{1} |
Пример выхода
3
0
3
45
1
РЕШЕНИЕ
динамическое
программирование
Обозначим через d[i][x]
количество подмножеств из i первых
кучек, для которых НОД равен x. В
таком случае ответом будет значение d[n][1],
где n – количество групп.
Поскольку подмножества из (i + 1) первых кучек включают в себя все
подмножества из i первых кучек, то
значение d[i][x] следует добавить к d[i + 1][x] для каждого x.
Пусть НОД некоторого подмножества
из i первых кучек равен x. При добавлении к нему (i + 1) - го элемента НОД полученного
подмножества станет равным НОД(x,
groups[i]) (индексы массива groups начинаются с нуля, первым элементом массива является
groups[0]). Поэтому значение d[i][x]
следует добавить к d[i + 1][НОД(x, groups[i])].
Перед началом обработки (i + 1) - ой кучки следует увеличить на 1
значение d[i + 1][groups[i]]: если игрок выберет только одну, (i + 1) - ую кучку, то НОД количества
монет в выбранных кучках равен groups[i].
Рассмотрим заполнение ячеек d[i][x]
для случая, когда groups = {2, 4, 3}:
|
i \ x |
1 |
2 |
3 |
4 |
|
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
1 |
0 |
0 |
|
2 |
0 |
2 |
0 |
1 |
|
3 |
3 |
2 |
1 |
1 |
При groups = {2, 5, 3, 4} массив d
будет иметь вид:
|
i \ x |
1 |
2 |
3 |
4 |
5 |
|
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
1 |
0 |
0 |
0 |
|
2 |
1 |
1 |
0 |
0 |
1 |
|
3 |
4 |
1 |
1 |
0 |
1 |
|
4 |
10 |
2 |
1 |
1 |
1 |
ПРОГРАММА
#include <cstdio>
#include <vector>
#include <memory>
using namespace std;
long long d[51][100001];
int gcd(int a, int b)
{
return a ? gcd(b%a,a) : b;
}
class DecorationDay
{
public:
int howMany(vector<int>
groups)
{
int i,j,n=(int)groups.size();
memset(d,0,sizeof(d));
for(i=1;i<=n;i++)
{
d[i][groups[i-1]]++;
for(j=1;j<=100000;j++)
{
d[i][gcd(j,groups[i-1])] += d[i-1][j];
d[i][j] += d[i-1][j];
}
}
return d[n][1] % 10000003;
}
};