মনে করুন, 'nums' নামে একটি n আকারের অ্যারে আছে যেটে পজিটিভ ইন্টিজার আছে। আমাদের কাছে 'queries' নামে আরেকটি অ্যারে আছে যেটে ইন্টিজার জোড়া (pi, qi) আছে। queries অ্যারেতে প্রতিটি কোয়েরির জন্য, উত্তর হবে nums[j] সংখ্যাগুলোর যোগফল যেখানে pi <= j < n এবং (j - pi) qi দ্বারা বিভাজ্য। আমাদের সব таких কোয়েরির উত্তর রিটার্ন করতে হবে, এবং যদি মান বড় হয় তবে মডুলো 10^9 + 7 দিয়ে রিটার্ন করুন।
সুতরাং, যদি ইনপুট হয় nums = [2, 3, 4, 5, 6, 7, 8, 9, 10], queries = [(2, 5), (7, 3), (6, 4)], তবে আউটপুট হবে [13, 9, 8]。
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব −
A := nums
Q := queries
n := nums-এর দৈর্ঘ্য
M := 10^9 + 7
m := (n ^ 0.5) এর ইন্টিজার মান + 2
P := A তালিকা m বার ধারণকারী একটি নতুন তালিকা
i = 1 থেকে m পর্যন্ত জন্য, করুন
j = n-1 থেকে -1 পর্যন্ত, ১ কমানো করে, করুন
যদি i+j < n হয়, তবে
P[i, j] := (P[i, j]+P[i, i+j]) modulo M
Q-এ প্রতিটি b, k-এর জন্য, করুন
যদি k < m হয়, তবে
[P[k, b]-এর ইনডেক্স থেকে মান] রিটার্ন করুন
অন্যথায়
[sum(A[b::k]) modulo M] রিটার্ন করুন
উদাহরণ
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন −
def solve(A, Q):
n, M = len(A), 10**9+7
m = int(n**0.5)+2
P = [A[:] for _ in range(m)]
for i in range(1,m):
for j in range(n-1,-1,-1):
if i+j < n:
P[i][j] = (P[i][j]+P[i][i+j]) % M
return [P[k][b] if k < m else sum(A[b::k]) % M for b, k in Q]
print(solve([2, 3, 4, 5, 6, 7, 8, 9, 10], [(2, 5), (7, 3), (6, 4)]))
ইনপুট
[2, 3, 4, 5, 6, 7, 8, 9, 10], [(2, 5), (7, 3), (6, 4)]
আউটপুট
[13, 9, 8]
