Блог

Постановка задачи: Дано на Hackrearth

Задан массив A из N целых чисел, и вы также определили новый массив B как объединение массива A бесконечное число раз. Например, если данный массив A равен [1,2,3] then, то бесконечный массив B равен [1,2,3,1,2,3,1,2,3,.......] .

Теперь вам дано Q запросов, каждый запрос состоит из двух целых L чисел и R . Ваша задача-найти сумму подмножества от индекса L до R (оба включительно) в бесконечном массиве B для каждого запроса.

Примечание: Поскольку значение этого вывода очень велико, выведите ответ в виде модуля 10^9 7;

Решение:

 vector<int> sumInRanges(vector<int> amp;arr, int n, vector<vector<long long>> amp;qrr, int q) {
   
    int mod=1e9 7;

    vector<long long>sarr(n 1,0);    // to store the prefix sum
    
    for(int i=1;i<=n;i  )
    {
        sarr[i]=(sarr[i-1] arr[i-1])%mod;
    }
    
    vector<int>ans;               //to store the final answer         
    
    for(int i=0;i<q;i  )
    {
        long long l,r;
        l=qrr[i][0];
        r=qrr[i][1];
        
        long long grp=(r/n)%mod;
        long long res=(grp*sarr[n])%mod;
        res=(res sarr[r%n])%mod;
        long long rsum=res;
        
        l-=1;
        grp=(l/n)%mod;
        res=(grp*sarr[n])%mod;
        res=(res sarr[l%n])%mod;
        long long lsum=res;

        int sum=((rsum-lsum mod)%mod);
        ------------------------------
        ans.push_back(sum);
    }

    return ans;
}
 

Мои сомнения:
Я решил данную проблему так, что я сначала нашел префикс такие суммы, а затем найти rsum расстояние до R, соответствующей бесконечное множество В и lsum до Л-1 соответствует бесконечное множество B, а затем найти окончательный ответ, (rsum - lsum)%mod но у меня есть некоторые тестовые случаи, как Вашингтон, но когда я сделал, как это (rsum - lsum mod)%mod все тесты случаев прошло, мои сомнения, это то, что какое значение имеет добавление «мод» в выделенную строку в растворе.