Комбинаторная задачка

[qrwmeq]

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

[Otta]

del

(Оффтоп)

provincialka

provincialka в сообщении #811145 писал(а):

Может, исходное сообщение было отредактировано?

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

[provincialka]

...

(Оффтоп)

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

[Aritaborian]

provincialka в сообщении #811145 писал(а):

Может, исходное сообщение было отредактировано?

Нет, не было. Если сообщение редактировали, рядом с его заголовком появляется сиреневый ромбик.
Вот такой: .
(Посмотрите на заголовок моего сообщения).

[iifat]

qrwmeq в сообщении #811121 писал(а):

$F((N = 3) 1,2,1)=6$

Странно как-то упорядочен сей кортеж. Это описка, или я чего-то не понимаю в условии?

-- 08.01.2014, 12:10 --

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

[bot]

(Оффтоп)

iifat в сообщении #811186 писал(а):

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

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

[Deggial]

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

[B@R5uk]

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

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

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

[VAL]

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)$ одинаковое число повторов, а ответы разные.

[Null]

Можно что-то типа такого:
Мы будем считать включая пустую строку в результат. Потом надо будет вычесть 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.

[qrwmeq]

Уже посылал абсолютно такое же решение, но прошло лишь половину тестов. Ошибка где-то при $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;
}

[Null]

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

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

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

[qrwmeq]

Вы абсолютно правы, спасибо вам за помощь, просто я брал отрицательное число по модулю (s=((2*s)%MOD-a[x])%MOD;), а оно программно вычисляется неправильно. Добавил функцию правильного взятия по модулю и вставил ее везде, где только можно. Результат - полный бал.

Используется синтаксис C++

ll mod(ll Z){
    if (Z<0) return Z+MOD;
    else return Z%MOD;
}

[Deggial]

Null, qrwmeq, замечание за неоформление формул.