|
|
|
|
|
|
|
Вернуться
| 1 Соболев Дима, 16 ноября 2009 г. 21:51:17 | |
Кстати, есть отличный ресурс с последовательностями http://www.research.att.com/~njas/sequences/
При вводе 2,18,90 в строку поиска единственная найденная последовательность является искомой.
|
|
|
| 2 Соболев Дима, 16 ноября 2009 г. 21:46:31 | |
Напишу как получить формулу. Рассмотрим 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,
во избежание переполнений.
|
|
|
| 3 Демиденко Виталий, 16 ноября 2009 г. 12:40:40 | |
|
Там вообще простая формула, но до неё докатить ещё надо
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
