رتبهی ۱۶۱ سال بعد: دوره چهار حلی سه کنکور دارند! رتبهی یک پارسال: اه!اه! پس ۱۶۰ تا…
- User
رتبهی ۱۶۱ سال بعد: دوره چهار حلی سه کنکور دارند!
رتبهی یک پارسال: اه!اه! پس ۱۶۰ تا بذار رو رتبت!
ما هم مثل شما نفهمیدیم این دیالوگ بالا برای چه وقتی بوده است! اما احتمالا ساختهی ذهن مریض طراح بوده و منبع موثقی ندارد! برای اینکه دیگر این مشکل پیش نیاید! میخواهیم جملههایی که شنیدهایم و به درست بودنشان اطمینان داریم را بازنویسی کنیم!!!
به این منظور جدولی n × m n×m تعبیه شده است. در سطر x x و ستون y y به اندازه ی max ( a + x × b , c + y × d ) max(a+x×b,c+y×d) جمله مینویسیم. حال مجموع تعداد جملهها را از شما میخواهیم.
در واقع برای همهی ستونها یک دنبالهی حسابی با قدر نسبت b b و مقدار اولیهی a a و برای همهی سطرها یک دنبالهی حسابی با قدر نسبت d d و مقدار اولیه c c در نظر گرفتیم و در هر خانه به تعداد بیشینه این دو عدد، جمله مینویسیم. شما باید جواب را که تعداد کل کلمه هاست به پیمانهی 1 0 9 + 7 10 9 +7 چاپ کنید.
ورودی در تنها خط ورودی به ترتیب اعداد n n، m m، a a، b b، c c و d d آمدهاند.
1 ≤ n , m ≤ 1
000
000
000 1≤n,m≤1 000 000 000
0 ≤ a , b , c , d ≤ 1
000
000 0≤a,b,c,d≤1 000 000
خروجی در تنها خط خروجی یک عدد به عنوان جواب مساله چاپ کنید.
مثال ورودی نمونه ۱ 3 3 0 1 0 2 Plain text خروجی نمونه ۱ 21 Plain text توضیح نمونه اول :
جفت ها عبارتند از:
(0,0) (0,2) (0,4) (1,0) (1,2) (1,4) (2,0) (2,2) (2,4) Plain text که مجموع بیشینههای هر جفت برابر با ۲۱ میشود.
ورودی نمونه ۲ 75164 100 97702 84646 95867 454 Plain text خروجی نمونه ۲ 997345518 c++
- Assistant
برای حل این مسئله، باید مجموع بیشینهی عبارات (max(a+x \times b, c+y \times d)) را محاسبه کنیم که (x) از 0 تا (n-1) و (y) از 0 تا (m-1) تغییر میکند. به این منظور باید برای هر (x)، تعداد ستونهایی ((y)) را محاسبه کنیم که برای آن (a+x \times b > c+y \times d) باشد. سپس تعداد ستونهایی را که شرط قبلی را نقض میکنند، محاسبه کرده و به تعداد آنها مقدار مورد نظر مربوط به (c+y \times d) را اضافه کنیم.
به صورت خلاصه، الگوریتم مورد نظر به این شرح است:
- برای هر سطر ((x))، ابتدا تعداد ستونهایی ((y)) را حساب کنید که برای آن (a + x \times b > c + y \times d) به جای (y) میگذارد.
- این شرط به صورت معادله به شکل (y < \dfrac{a + x \times b - c}{d}) درمیآید.
- اگر (d = 0) بود و (a + x \times b > c)، آنگاه برای تمام (y)ها جواب را مطابق (a + x \times b) معادل سازی میکنیم. 4.مقداری که از مرحله قبل به دست آمده را در (a + x \times b) ضرب کرده و به مجموع اضافه میکنیم.
- برای باقی ستونها ((m \text{ mod } d) ستون دیگر)، مقدار (c + y \times d) را از (y = \dfrac{a + x \times b - c}{d}) تا (m-1) برداشته و به مجموع اضافه کنید.
- نتیجه را به پیمانهی (10^9+7) در نظر گرفته و در خروجی چاپ کنید.
در پیاده سازی نهایی، برای محاسبه سریع معادلات حسابی از تغییرات حسابی به جای استفاده از حلقه استفاده میشود.
متن نهایی کد به زبان برنامهنویسی C++:
#include <iostream> using namespace std; const int MOD = 1e9 + 7; int main() { long long n, m, a, b, c, d; cin >> n >> m >> a >> b >> c >> d; long long totalSum = 0; for (long long x = 0; x < n; ++x) { long long A = a + x * b; if (d == 0) { if (A > c) { totalSum = (totalSum + m * A) % MOD; } else { totalSum = (totalSum + m * c) % MOD; } } else { long long y_limit = (A - c) / d; if (y_limit < 0) { y_limit = 0; totalSum = (totalSum + m * c) % MOD; } else if (y_limit >= m) { y_limit = m - 1; totalSum = (totalSum + m * A) % MOD; } else { totalSum = (totalSum + (y_limit + 1) * A) % MOD; long long remaining = m - (y_limit + 1); long long start_c = c + (y_limit + 1) * d; long long end_c = c + (m - 1) * d; long long sumC = ((start_c + end_c) * remaining) / 2; sumC %= MOD; totalSum = (totalSum + sumC) % MOD; } } } cout << totalSum << endl; return 0; }این الگوریتم به واسطه استفاده از محاسبه دنباله حسابی، میتواند در زمان مناسبی برای محدودههای بزرگ داده شده (n) و (m) اجرا شود.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.