آمار پرسش:
- پرسیده شده: 2015-01-11 01:32:58 -0500
- مشاهده شده: 514 بار
- بروز شده: 2015-01-11 23:32:18 -0500
پرسش‌های مشابه:
رتینگ در codeforces و سوالات در حد دوره و مرحله 3
وبسایت مسابقه‌های برنامه نویسی
یافتن کوتاه ترین دور در گراف ساده
کد مساله هشت وزیر با استفاده از الگوریتم ژنتیک
مرجع فارسی برای الگوریتم های هندسی و 2sat
نظریه اعداد لازم برای المپیاد کامپیوتری ها
برای مرحله سوم، تا چه سطحی باید برنامه نویسی بلد باشیم؟
اولین جمله از دنباله ی فیبوناچی که 1000رقم داشته باشد چیست؟
نکاتی در مورد نوشتن پاسخ:
استفاده از ویرایشگر:
علائم ریاضی:
سوال برنامه نویسی بسط سه جمله ای(گمون نکنم!)
سلام. در بسط سه جمله ای زیر ضریب $x^i$
را mode 3 به دست آورید.
$(x^2+x+1)^n$
$10^{15} \ge n\ge 0 $
محدودیت زمان:1 ثانیه محدودیت حافظه :32 مگ
2015-01-11 01:32:58 -0500
کریمینال 283 ● 6 ● 9 ● 19
نظرات
1 پاسخ
خب اول توی پرانتز رو دستکاری می کنیم:
$(x^2 +x+1)^n = ((x-1)^2-3x)^n$
چون سوال جوابو به صورت $\pmod 3$ می خواد پس $3x$ تاثیری ندارد پس می ماند $((x-1)^2)^n$ یا $(x-1)^{2n}$
برای این قسمت هم از قضیه لوکا استفاده می کنیم که:
$\binom{m}{n} \equiv \prod_{i=0}^k\binom{m_i}{n_i}\pmod p $
$m = m_kp^k +m_{k-1}p^{k-1}+...+m_1p^1+m_0p^0$(مبنای 3 عدد $m$)
$n = n_kp^k +n_{k-1}p^{k-1}+...+n_1p^1+n_0p^0$(مبنای 3 عدد $n$)
پس کافی است که اعداد رو در مبنای 3 ببریم.ودر رابطه ی بالا ببریم که در آن:
$m = 2n ,n = k$
حواستون به منفی و مثبت ها هم باشه
اینم کد خودم.
2015-01-11 12:06:28 -0500
پوبا 780 ● 3 ● 13 ● 22
نظرات