Вычислить сумму "произведения"

[Rusl92]

Здравствуйте, форумчане, не могли бы вы мне помочь решить такую задачу:

Вводим n и m
Вычислить Sn такое что
Sn = Сумма k от 0 до n-1 (k^2 * 2^k)

{сумма произведения k в квадрате и 2 в степени k, где k [0..n-1]}

Ответ вывести по модулю m

Пример:
1) 1 1000 - 0
2) 2 1000 - 2
3) 8 427 - 328

дело в том что n может быть от 0 до 10^9
а m от 1 до 10^9

то есть в данном случае вcтает проблема хранения этого Sn
не могли бы вы сказать, где можно будет хранить такое большое число?
заранее спасибо!

[LeBron]

Хм Весело, при такой задаче задавать такие вопросы. По поводу хранения числа - проблем вообще никаких, в процессе вычисления Вам не понадобяться типы для хранения чисел, больших за 10^18, так что любая восьмибайтовка подходит. Другое дело, если надо решить задачу.. Что ж, тогда дам разбор (напишите, надо или нет). А задачка ведь не совсем детская, я бы сказал - средней сложности, кроме базовых алгоритмов она требует еще и знания школьного курса математики (чем могут похвалиться немногие). По крайней мере, это самая сложная задача из всех, которые выкладывали в этом разделе за последнюю неделю.

[Rusl92]

хорошо было бы посмотреть разбор!
и тип результата

тут как я понял какие-то преобразования требуются?

[LeBron]

Да. А зачем Вам эта задача? Интересно стало.
Тип - любая восьмибайтовка, не знаю, в чем вы собираетесь это писать, если, к примеру, в плюсах - то long long. Задача была на четвертьфинале NEERC этого года (из всех задач четвертьфинала (8 штук) она мне кажеться второй или третей по сложности). Копирую Вам простой, понятный, и сильно разжеваный разбор by sdya:

Напишу как получить формулу. Рассмотрим S[n+1]=sum(i^2*2^i), где i от 0 до n.
Воспользуемся тождеством i^2=1+3+5+...+(2*i-1).
Имеем S[n+1]=sum((1+3+..+(2*i-1))*2^i), где i от 0 до n. Далее
S[n+1]=1*(2^1+2^2+...+2^n)+3*(2^2+2^3+... +2^n)+ ... +(2*i-1)*(2^i+2^(i+1)+...+2^n)+...+(2*n-1)*(2^n).
Слагаемое c i=0 мы выкинем, так как 0^2*2^0=0. Далее по формуле суммы геометрической прогресси имеем
S[n+1]=(2-1)*(2^(n+1)-2^1)+ ... +(2*i-1)*(2^(n+1)-2^i)+ ... +(2*n-1)*(2^(n+1)-2^n). Упрощаем:
S[n+1]=(1+3+..+(2*n-1))*2^(n+1) + (2^1+2^2+...+2^n) - 2*(1*2^1+2*2^2+3*2^3+...+n*2^n).
Сумма 1+3+...+(2*n-1)=n^2, 2^1+2^2+...2^n=2^(n+1)-2.
1*2^1+2*2^2+3*2^3+...+n*2^n = (2^1+2^2+...+2^n)+(2^2+2^3+...+2^n) + ... +(2^(n-1)+2^n)+(2^n)=
=(2^(n+1)-2)+(2^(n+1)-2^2)+...+(2^(n+1)-2^n) = n*2^(n+1)-(2+2^2+...+2^n)=n*2^(n+1)-2^(n+1)+2=
=(n-1)*2^(n+1)+2. Объединяя результаты имеем
S[n+1]=n^2*2^(n+1)+2^(n+1)-2-2*((n-1)*2^(n+1)+2) = (n^2+1-2*(n-1))*2^(n+1)-2-4=(n^2-2*n+3)*2^(n+1)-6.
Таким образом, имеем формулу S[n+1] = (n*n-2*n+3)*2^(n+1)-6.
Соответственно S[n] = ((n-1)*(n-1)-2*(n-1)+3)*2^n-6=(n*n-4*n+6)*2^n-6.
Ну а это число уже легко посчитать по модулю m.
2^n mod m считаем при помощи быстрого возведения в степень за O(lg n),
а остальное напрямую. Единственное нужно не забыть использовать long long в C++ или Int64 в Pascal,
во избежание переполнений.

[Rusl92]

спасибо огромное!

program Project1;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var n,m:longint;
    t:int64;
    input,output:text;
function power(a:int64;n1:longint):int64;
var res:int64;
begin
    if odd(n1) then res:=a else res:=1;
    while (n1>1) do
     begin
        n1:=n1 div 2;
        a:=((a*a) mod m);
        if odd(n1) then res:=((res*a)mod m);
     end;
    power:=res;
end;
begin
   assign(input,'input.txt');
   reset(input);
   assign(output,'output.txt');
   rewrite(output);
   read(input,n,m);
   t:=power(2,n);
   t:=((n*n-4*n+6)*t-6) mod m;
   write(output,t);
   close(input);
   close(output);

end.

заваливается на 4 тесте
не подскажите, что тут может быть неверно?

[LeBron]

И после исправления - все равно переполнение. Только теперь в другом месте. Скажете АСМ-систему - укажу, где ошибка.
З.Ы. Ответ в личку понял. Ошибка вот сдесь:

t:=((n*n-4*n+6)*t-6) mod m;

Тоже переполнение.

[Lemo]

Пошагово пройдитесь F7, просматривая переменные и будет вам счастье=)

[Rusl92]

v:int64;

...

v:=((n*n) mod m);
t:=(((v-4*n+6) mod m)*t) mod m-6) mod m;
так?

исправил и это переполнение
теперь конечный вид кода:

program Project1;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var n,m:longint;
    t,v:int64;
    input,output:text;
function power(a:int64;n1:longint):int64;
var res:int64;
begin
    if odd(n1) then res:=a else res:=1;
    while (n1>1) do
     begin
        n1:=n1 div 2;
        a:=((a*a) mod m);
        if odd(n1) then res:=((res*a)mod m);
     end;
    power:=res;
end;
begin
   assign(input,'input.txt');
   reset(input);
   assign(output,'output.txt');
   rewrite(output);
   read(input,n,m);
   t:=power(2,n);
   v:=n*n;
   t:=((((v-4*n+6)mod m) *t-6) mod m) mod m;
   write(output,t);
   close(input);
   close(output);

end.

опять ошибка на 4 тесте
здесь уже нет мест - где возможно переполнение!
помогите найти ошибку(

[LeBron]

Сообщение от Rusl92

v:int64;

...

v:=((n*n) mod m);
t:=(((v-4*n+6) mod m)*t) mod m-6) mod m;
так?

Что за народ пошел... Вместо того, что бы решать задачи... эх...
Да как угодно, главное, что бы без переполнения.

[Rusl92]

да уж
задача решена
а "accepted" выдавать не хочет
странно оч
проходит стандартные тесты
все аккуратно теперь прослежено

что же делать?