2014 dxdy logo

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

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




 
 Комбинаторная задачка
Сообщение08.01.2014, 00:00 
Здравствуйте!
Недавно наткнулся на задачу и никак не могу получить ответ для общего случая. Дан упорядоченный список (кортеж) из $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 
del

(Оффтоп)

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

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

 
 
 
 Re: Комбинаторная задачка
Сообщение08.01.2014, 00:54 
Аватара пользователя
...

(Оффтоп)

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

 
 
 
 Сообщение было отредактировано.
Сообщение08.01.2014, 00:59 
Аватара пользователя
provincialka в сообщении #811145 писал(а):
Может, исходное сообщение было отредактировано?
Нет, не было. Если сообщение редактировали, рядом с его заголовком появляется сиреневый ромбик.
Вот такой: Изображение.
(Посмотрите на заголовок моего сообщения).

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

-- 08.01.2014, 12:10 --

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

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

(Оффтоп)

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

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

 
 
 
 Re: Комбинаторная задачка
Сообщение08.01.2014, 07:01 
Аватара пользователя
 i  qrwmeq, наведите мышью на свои формулы, посмотрите в хинте, как пишутся в $\TeX$е фигурные скобки.

 
 
 
 Re: Комбинаторная задачка
Сообщение08.01.2014, 08:42 
Аватара пользователя
Если в исходном упорядоченном множестве количество элементов равно $N$ и все эти элементы разные, то количество комбинаций $S_N$ равно

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

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

 
 
 
 Re: Комбинаторная задачка
Сообщение08.01.2014, 11:08 
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 
Можно что-то типа такого:
Мы будем считать включая пустую строку в результат. Потом надо будет вычесть 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 
Уже посылал абсолютно такое же решение, но прошло лишь половину тестов. Ошибка где-то при $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 
А у вас в $s=(2*s)%MOD-a[x];$ отрицательное получиться не может?

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

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

 
 
 
 Re: Комбинаторная задачка
Сообщение13.01.2014, 14:20 
Вы абсолютно правы, спасибо вам за помощь, просто я брал отрицательное число по модулю (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 
Аватара пользователя
 !  Null, qrwmeq, замечание за неоформление формул.

 
 
 [ Сообщений: 14 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group