Вычислить сумму i ^ 2 * C (n, i), 0 <= i <= n, 1 <= n <= 10 ^ 18 - PullRequest
Новая
       76

Вычислить сумму i ^ 2 * C (n, i), 0 <= i <= n, 1 <= n <= 10 ^ 18

0 голосов
/ 06 мая 2018

Найти ответ мод 1e9 + 7 в срок 1 секунда. C (n, i) равно числу способов выбора элементов i из n различных элементов (игнорируя порядок).

Ответы [ 2 ]

0 голосов
/ 25 июля 2018

Лукас может решить этот вопрос, я думаю, что основной код - это Лукас, вы можете выучить Лукас на веб-сайте, легко получить код. И после этого вы можете решить его как простой вопрос.

Например: 

LL Lucas(LL a, LL b)
{
    if(a < mod && b < mod)
        return C(a, b);
    return
        C(a % mod, b % mod) * Lucas(a / mod, b / mod);
}

Вот блог про Лукаса: https://blog.csdn.net/acdreamers/article/details/8037918

Если у вас есть другие вопросы, вы можете ответить на них.

Я предлагаю изучить алгоритм Лукаса, и вы можете что-то получить.

0 голосов
/ 06 мая 2018

Используя генерирующую функцию, я полагаю, что вы можете показать, что сумма может быть оценена точно как n(n_2)*(2^(n-2)).

Это можно получить, переписав сумму в следующей форме:

enter image description here

Это суммирование можно упростить, признав его просто биномиальным разложением

enter image description here

, который можно дифференцировать дважды по альфа и оценивать при альфа = 0, что дает

enter image description here

Мы можем проверить, что эта формула дает правильный результат с помощью простого скрипта Python: 

import numpy, scipy.misc

def fn(n):
    i = numpy.arange(0, n+1)
    combs = scipy.misc.comb(n, i)
    return numpy.sum((i**2) * combs)

def fn2(n):
    return n*(n+1) * (2 ** (n-2))


for n in range(1, 20):
    print('n={}, raw-sum={}, ratio={}' \
            .format(n, fn(n), (fn2(n) / fn(n))))

, который производит следующий вывод: 

n=1, raw-sum=1.0, ratio=1.0
n=2, raw-sum=6.0, ratio=1.0
n=3, raw-sum=24.0, ratio=1.0
n=4, raw-sum=80.0, ratio=1.0
n=5, raw-sum=240.0, ratio=1.0
n=6, raw-sum=672.0, ratio=1.0
n=7, raw-sum=1792.0, ratio=1.0
n=8, raw-sum=4608.0, ratio=1.0
n=9, raw-sum=11520.0, ratio=1.0
n=10, raw-sum=28160.0, ratio=1.0
n=11, raw-sum=67584.0, ratio=1.0
n=12, raw-sum=159744.0, ratio=1.0
n=13, raw-sum=372736.0, ratio=1.0
n=14, raw-sum=860160.0, ratio=1.0
n=15, raw-sum=1966080.0, ratio=1.0
n=16, raw-sum=4456448.0, ratio=1.0
n=17, raw-sum=10027008.0, ratio=1.0
n=18, raw-sum=22413312.0, ratio=1.0
n=19, raw-sum=49807360.0, ratio=1.0

Тогда будет просто вычислить желаемый результат по модулю (1e9 + 7), используя метод повторное возведение в квадрат для вычисления 2 ^ x, уменьшая все умножения по модулю (1e9 + 7) на каждом этапе расчета.

...