2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Комбинаторная задачка
Сообщение08.01.2014, 00:00 


07/01/14
3
Здравствуйте!
Недавно наткнулся на задачу и никак не могу получить ответ для общего случая. Дан упорядоченный список (кортеж) из $N$ элементов. Необходимо за разумное время (ессесно не полный перебор) сосчитать количество всех возможных различных непустых "подсписков", т.е таких, в которые можно получить из данного удалением некоторых элементов. Примеры:
$F((N = 3) 1,2,3)=7 \ (\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\})$
$F((N = 3) 1,2,1)=6 \ (\{1\},\{2\},\{1,2\},\{1,1\},\{2,1\},\{1,2,1\})$
$F((N = 2) 7,7)=2 \ (\{7\},\{7,7\})$
Требуется решение, ассимптотически не превышаюшее $O(N \log N)$. (Но тут, кажется, есть решение за линию). Мощность множества возможных значений элементов не превышает $10^6$.

 Профиль  
                  
 
 Re: Комбинаторная задачка
Сообщение08.01.2014, 00:37 
Заслуженный участник


09/05/13
8904
del

(Оффтоп)

provincialka
provincialka в сообщении #811145 писал(а):
Может, исходное сообщение было отредактировано?

Не, это я не поняла.

 Профиль  
                  
 
 Re: Комбинаторная задачка
Сообщение08.01.2014, 00:54 
Заслуженный участник
Аватара пользователя


18/01/13
12044
Казань
...

(Оффтоп)

Может, исходное сообщение было отредактировано? Там все понятно. То есть условие понятно.

 Профиль  
                  
 
 Сообщение было отредактировано.
Сообщение08.01.2014, 00:59 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
provincialka в сообщении #811145 писал(а):
Может, исходное сообщение было отредактировано?
Нет, не было. Если сообщение редактировали, рядом с его заголовком появляется сиреневый ромбик.
Вот такой: Изображение.
(Посмотрите на заголовок моего сообщения).

 Профиль  
                  
 
 Re: Комбинаторная задачка
Сообщение08.01.2014, 04:06 
Заслуженный участник


16/02/13
4105
Владивосток
qrwmeq в сообщении #811121 писал(а):
$F((N = 3) 1,2,1)=6$
Странно как-то упорядочен сей кортеж. Это описка, или я чего-то не понимаю в условии?

-- 08.01.2014, 12:10 --

На случай описки: для непересекающихся кортежей соотношение между функциями от кортежей и функцией от объединения кортежей достаточно очевидно. Особенно если не исключать пустого подмножества — единицу можно быстренько вычесть уже в самом конце.

 Профиль  
                  
 
 Re: Комбинаторная задачка
Сообщение08.01.2014, 06:19 
Заслуженный участник
Аватара пользователя


21/12/05
5904
Новосибирск

(Оффтоп)

iifat в сообщении #811186 писал(а):
qrwmeq в сообщении #811121
писал(а):
$F((N = 3) 1,2,1)=6$ Странно как-то упорядочен сей кортеж. Это описка, или я чего-то не понимаю в условии?

А чего ж тут не понять? Слева функция трёх аргументов с аргументами $\ (N=3)1, \ 2 \ \text{и} \ 1$, справа тоже функция шести аргументов, обозначенная символом $6$

 Профиль  
                  
 
 Re: Комбинаторная задачка
Сообщение08.01.2014, 07:01 
Супермодератор
Аватара пользователя


20/11/12
5728
 i  qrwmeq, наведите мышью на свои формулы, посмотрите в хинте, как пишутся в $\TeX$е фигурные скобки.

 Профиль  
                  
 
 Re: Комбинаторная задачка
Сообщение08.01.2014, 08:42 
Аватара пользователя


26/05/12
1534
приходит весна?
Если в исходном упорядоченном множестве количество элементов равно $N$ и все эти элементы разные, то количество комбинаций $S_N$ равно

$S_N=\sum\limits_{k=1}^{N}{C_N^k}=2^N-1$

Если же элементы повторяются, то надо каждый из этих коэффициентов разделить на подходящую величину.

 Профиль  
                  
 
 Re: Комбинаторная задачка
Сообщение08.01.2014, 11:08 
Заслуженный участник


27/06/08
4058
Волгоград
B@R5uk в сообщении #811207 писал(а):
Если в исходном упорядоченном множестве количество элементов равно $N$ и все эти элементы разные, то количество комбинаций $S_N$ равно

$S_N=\sum\limits_{k=1}^{N}{C_N^k}=2^N-1$

Если же элементы повторяются, то надо каждый из этих коэффициентов разделить на подходящую величину.
Не все так просто.
В наборах $(1,6,1)$ и $(1,1,6)$ одинаковое число повторов, а ответы разные.

 Профиль  
                  
 
 Re: Комбинаторная задачка
Сообщение08.01.2014, 16:32 
Заслуженный участник


12/08/10
1608
Можно что-то типа такого:
Мы будем считать включая пустую строку в результат. Потом надо будет вычесть 1.
Для пустой строки результат 1.
Добавим символ
1. он новый -> результат удвоим
2. он уже был -> удвоим результат и вычтем из того что получилось результат перед предыдущим(последним из них ) таким же числом.

Можно хранить массив результатов для каждого числа(и 0 для тех чисел которых небыло). Пусть возможных значений элементов $M$. Есть 2 варианта:
1.Храним массив длинны $M$. Сложность $M+N(\cdot N)$-считать придется в длинной арифметике.
2.Считываем возможное множество значений и сортируем его. Заводим 2рой массив для соответствующих результатов. Используем его для хранения данных.Сложность $N \ln N(\cdot N)$-считать придется в длинной арифметике.

Например:
1,2,1,1,2
k=0
Результат: 1, Результат перед 1: 0,Результат перед 2: 0
k=1
Результат: 2, Результат перед 1: 1,Результат перед 2: 0
k=2
Результат: 4, Результат перед 1: 1,Результат перед 2: 2
k=3
Результат: 7=8-1, Результат перед 1: 4,Результат перед 2: 2
k=4
Результат: 10=14-4, Результат перед 1: 7,Результат перед 2: 2
k=5
Результат: 18=20-2, Результат перед 1: 7,Результат перед 2: 10
Ответ 17=18-1.

 Профиль  
                  
 
 Re: Комбинаторная задачка
Сообщение13.01.2014, 00:14 


07/01/14
3
Уже посылал абсолютно такое же решение, но прошло лишь половину тестов. Ошибка где-то при $N=100$. И да, кстати, решение надо было выводить по модулю $10^9+7$.
Вот, если интересно, код.
код: [ скачать ] [ спрятать ]
Используется синтаксис C++
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <climits>
#include <set>
using namespace std;
#define c(i,s,f) for(int i=s;i<=f;i++)
#define pb push_back
typedef unsigned long long int ull;
const ull MOD=1000000007;
ull N,s,pl,x,ss;
vector<ull> a;
int main(){
    cin>>N;
    s=1ull;
    a.assign(1000001,0ull);
    c(i,1,N){
        cin>>x;
        ss=s;
        s=(2*s)%MOD-a[x];
        a[x]+=(s-ss);
        a[x]%=MOD;
    }
    cout<<(s-1)%MOD;
}

 Профиль  
                  
 
 Re: Комбинаторная задачка
Сообщение13.01.2014, 07:07 
Заслуженный участник


12/08/10
1608
А у вас в $s=(2*s)%MOD-a[x];$ отрицательное получиться не может?

-- Пн янв 13, 2014 08:08:24 --

s=(2*s)%MOD-a[x];

 Профиль  
                  
 
 Re: Комбинаторная задачка
Сообщение13.01.2014, 14:20 


07/01/14
3
Вы абсолютно правы, спасибо вам за помощь, просто я брал отрицательное число по модулю (s=((2*s)%MOD-a[x])%MOD;), а оно программно вычисляется неправильно. Добавил функцию правильного взятия по модулю и вставил ее везде, где только можно. Результат - полный бал.
Используется синтаксис C++
ll mod(ll Z){
    if (Z<0) return Z+MOD;
    else return Z%MOD;
}

 Профиль  
                  
 
 Re: Комбинаторная задачка
Сообщение13.01.2014, 16:48 
Супермодератор
Аватара пользователя


20/11/12
5728
 !  Null, qrwmeq, замечание за неоформление формул.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group