1714. Sum Of Special Evenly-Spaced Elements In Array

You are given a 0-indexed integer array nums consisting of n non-negative integers.

You are also given an array queries, where queries[i] = [xi, yi]. The answer to the ith query is the sum of all nums[j] where xi <= j < n and (j - xi) is divisible by yi.

Return an array answer where answer.length == queries.length and answer[i] is the answer to the ith query modulo 109 + 7.

class Solution {
    int mod = 1e9 + 7;
    int dp[224][50000];
    unordered_map<int, unordered_map<int, int>> lazyProp;
    int query(vector<int>& A, int start, int append) {
        int res = 0;
        for(int i = start; i < A.size(); i += append) {
            res = (res + A[i]) % mod;
        }
        return res;
    }
    void helper(vector<int>& A, int y, int lazy, int until) {
        int n = A.size();
        for(int i = lazy; i >= until; i-=y) {
            dp[y][i] = (A[i] + (i + y < n ? dp[y][i + y] : 0)) % mod;
        }
    }
    int preQuery(vector<int>& nums, int startAt, int y) {
        int remain = startAt % y;
        int lazy = ceil(1.0 * nums.size() / y) * y + remain - y;
        if(lazy >= nums.size()) lazy -= y;
        if(lazyProp.count(y) and lazyProp[y].count(remain)) {
            lazy = min(lazy, lazyProp[y][remain]);
        } else lazyProp[y][remain] = lazy;
        if(lazy >= startAt)
            helper(nums, y, lazy, startAt);
        lazyProp[y][remain] = min(lazyProp[y][remain], startAt);
        return dp[y][startAt];
    }
public:
    vector<int> solve(vector<int>& nums, vector<vector<int>>& queries) {
        memset(dp, 0, sizeof dp);
        vector<int> res;
        int sq = sqrt(nums.size());
        for(auto& q: queries) {
            if(q[1] > sq)
                res.push_back(query(nums, q[0], q[1]));
            else
                res.push_back(preQuery(nums, q[0], q[1]));
        }
        return res;
    }
};