0

Решал следующую задачу: Вам нужно научиться отвечать на запрос “сумма чисел на отрезке”. Массив не меняется. Запросов много. Отвечать на 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 бит. Пожалуйста, объясните как мне это сделать.

1
  • Чтобы оставить младшие 30 бит от числа unsigned int x; (на мой взгляд, беззнаковое Вам подойдёт), нужно сделать так: unsigned int y = x | 0x3FFFFFFF;, тогда в y останутся младшие 30 бит. Здесь мы просто применяем операцию побитового логического ИЛИ с числом, которое в двоичном виде выглядит как 30 единиц. Это распространённый способ "отсечения" нужной части бит от числа.
    – V-Mor
    19 авг 2021 в 1:11

1 ответ 1

0

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

Сама формула для 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)

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.