Задача rsq. Взятие числа по модулю

Question

Решал следующую задачу: Вам нужно научиться отвечать на запрос “сумма чисел на отрезке”. Массив не меняется. Запросов много. Отвечать на 1 запрос следует за O ( 1 ) .

Формат ввода: Размер массива - n и числа x,y,a0, порождающие массив a: ai=(xai-1+y) mod 2^16. Далее следует количество запросов m и числа z,t,b0, порождающие массив b: bi=(zbi-1+t) mod 2^30, ci=bi mod n. i-й запрос - найти сумму на отрезке от min(c2i,c2i+1) до max(c2i,c2i+1) в массиве a. Ограничения: 1<=n<=10^7, 0 <=m<=10^7. Все числа целые от 0 до 2^16. t может быть -1.

Формат вывода: выведите сумму всех сумм.

Вот мой код:

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);


    ll n,x,y,a0;
    cin>>n>>x>>y>>a0;

    vector<unsigned long long> a(n+1);
    a[1]=a0;

    for (int i=2;i<=n;++i)
        a[i]=(x*a[i-1]+y)&((1<<16)-1);

    ll m,z,t,b0;
    cin>>m>>z>>t>>b0;


    vector<unsigned long long> b(2*n+1);
    b[1]=b0;

    for (int i=2;i<=2*n;++i)
        b[i]=(z*b[i-1]+t)&((1<<30)-1);

    unsigned long long ans=0;
    vector<unsigned long long> pref(n+1);

    for (int i=1;i<=n;++i)
            pref[i]=pref[i-1]+a[i];

    for (int i=0;i<m;++i)
        ans+=pref[max(b[2*i+1]%n,b[2*i+2]%n)+1]-pref[min(b[2*i+1]%n,b[2*i+2]%n)];

    cout<<ans<<'\n';


    return 0;
}

Программа проходит несколько тестов, а затем выдает неправильный результат, скорее всего из - за переполнений, поэтому пробовал поставить unsigned long long. Также в конце условия есть замечание: Заметим, что вместо того, Чтобы брать по модулю 2^30, достаточно все считать в типе int и оставлять младшие 30 бит. Пожалуйста, объясните как мне это сделать.

Answer 1

Эта задача не на мастерство владения С++, а на подумать.

Сама формула для a_i намекает, что это задача на сумму геометрической прогрессии. Поэтому перед тем, как писать программу, стоит сначала вывести формулу для a_i и для суммы a_i.

a_1 = x*a_0 + y
a_2 = x*a_1 + y = x^2 *a_0 + x*y + y
a_3 = x*a_2 + y = x^3 *a_0 + x^2*y + x*y + y = a*x^3 * y*(x^3 - 1)/(x-1)

Как бы намекает, что a_n = a*x^n * y*(x^n - 1)/(x-1) = (a+y/(x-1))*x^n - y/(x-1)

b_i находятся по аналогичной формуле.

Теперь можно получить формулу для суммы a_0 + a_1 + .. + a_n:

S(n) = (a+y/(x-1))*(x^(n+1) - 1)/(x-1) - (n+1)*y/(x-1)
     = [(a+y/(x-1))*(x^(n+1) - 1) - (n+1)*y]/(x-1)

Зная S(n) сумма по интервалу от c1 до c2 будет S(c2) - S(c1). Так достигается константное время вычисления o(1)

БЛОГ НА HUSL

Задача rsq. Взятие числа по модулю

Ответы (1 шт):