I have a doubt about how devide polynomial in NTT.Specifically in this problem link :https://www.codechef.com/JULY16/problems/POLYEVAL/ In editorial and many solution,they are deviding polynomial into 3 polynomials as A(x^3)+xA(x^3)+x^2A(x^3). I didn't understand why it is needed to devide the polynomial into 3 polynomial first and then apply NTT. Can we take whole polynomial into single array and do it's NTT.Please Clarify my doubt.
→ Обратите внимание
До соревнования
Helvetic Coding Contest 2024 online mirror (teams allowed, unrated)
33:20:59
Зарегистрироваться »
Helvetic Coding Contest 2024 online mirror (teams allowed, unrated)
33:20:59
Зарегистрироваться »
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 165 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 160 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | orz | 146 |
| 9 | SecondThread | 145 |
| 9 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 03.05.2024 00:44:01 (k2).
Десктопная версия, переключиться на мобильную.
При поддержке
Only LiTi understood FFT and NTT. Ask him.
We're waiting for you, LiTi
LiTi Can you please explain it??
LiTi, don't keep us waiting!
You're everywhere for free upvotes, aren't you Swistakk? :P I hope that LiTi will come soon and make everything clear.
Guys, LiTi has spoken !
seems legit
So +100 upvotes!
We want LiTi explain NTT for us!
Come on people, LiTi needs help, his battle strategy didn't go as expected
If only I knew English, I could say if this translation is fake.
seems more legit
mod = 3*2^18+1 . its convenient to divide it into three portions so that size of each portion is a power of 2 . you can even initially form three polynomials each of size 2^18 and perform NTT on all three of them so that they finally produce values for 3*2^18 distinct points.
Why is it needed to decompose in 3 polynomials ?? Can we concat 2^18 zeroes so that final polynomial becomes of 2^20 ie 4*(2^18) numbers which is perfect square and do NTT??
Because the mod is 3*2^18+1 so you can't find a primitive root that gives a cycle of size 2^20, the limit is 2^18
Thank you very much.Finally I got it.
Wondering if LiTi will approve this.
So maybe on his birthday, LiTi will be willing to explain NTT? Happy birthday, LiTi :)
PS: We are waiting for you :D
To the glory of my birthday, I will approve Arunnsit's solution!!