Processing math: 7%

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۶:عملی مقدماتی اول:سوال ۲

هنگ ۳(mod۳)

توابع f:N{1,1} و g:NZ به صورت زیر تعریف می‌شوند:

\begin{equation*} f(n)= \begin{cases} 1, & n \equiv 1 \pmod 3 \\ -1, & n \equiv 2 \pmod 3 \\ f(\frac{n}{3}), & n \equiv 0 \pmod 3 \\ \end{cases} \end{equation*}

\begin{equation*} g(n)=\sum_{i=1}^{n}f(i) \end{equation*}

در توضیحات بالا، منظور از \mathbb{N} مجموعه‌ی اعداد طبیعی و منظور از \mathbb{Z} مجموعه‌ی اعداد صحیح است.

برنامه‌ای بنویسید که q پرسمان به صورت (l,r) دریافت کند و به ازای هر پرسمان تعداد نابجایی‌های دنباله‌ی g(l), g(l+1), \ldots, g(r) را محاسبه کند. با توجه به این‌که پاسخ پرسمان‌ها می‌تواند بزرگ باشد، باقی‌مانده‌ی آن بر 10^9 + 7 را محاسبه کنید.

تعداد نابجایی‌های دنباله‌ی a_1, a_2, \ldots, a_n برابر است با تعداد جفت (i,j) هایی که i < j و a_i > a_j است.

ورودی

در سطر اول ورودی عدد طبیعی q، تعداد پرسمان‌ها، آمده است.

در هر یک از q سطر بعدی به ترتیب دو عدد طبیعی l و r آمده است.

خروجی

خروجی شامل q سطر است که در i امین (1\leq i\leq q) سطر از آن، پاسخ پرسمان i ام آمده است.

زیرمسئله‌ها

  • زیرمسئله اول (۲۵ نمره): l,r \leq 10^6
  • زیرمسئله دوم (۲۵ نمره): r - l \leq 100, q \leq 10^4
  • زیرمسئله سوم (۵۰ نمره): بدون محدودیت اضافی

محدودیت‌ها

  • محدودیت زمان: ۲ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت
  • 1\leq q\leq 5\times 10^4
  • 1\leq l \leq r\leq 10^{18}

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
4
1 1
2 3
1 5
3 17
0
0
2
25

ابزار صفحه