I have noticed that educational rounds like to use mod 998244353 instead of mod 109 + 7. Does anyone know the reason for this? One idea that comes to mind is since 998244353 < 109 there might be opportunities to troll contestants by breaking division and forcing them to calculate things like 
mod 998244353. However I have yet to see this used in an educational round, although this idea was used to good effect in 272D - Dima and Two Sequences.
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
4 дня
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 166 |
| 2 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 19.11.2024 13:33:31 (l2).
Десктопная версия, переключиться на мобильную.
При поддержке
As far as I know, 998244353 allows you to do interesting stuff related to polynomial multiplication I haven't fully studied yet. See this CF tutorial and this note in Petr's blog.
Other times, 998244353 is used because it's prime, much like 109 + 7, or 109 + 9, or 106 + 69. There can also be a mind-game factor involved: one time, I thought a problem needed the above tricks to be solved simply because the modulo was 998244353, but in the end, I was fooled!
Why it appears often in educational rounds? I don't know, you'll have to ask the setters for that.
This is nice because it lets you do Fast Fourier Transforms (mod p) using only the integers. In other words, the setters don't want to give away whether the problem is supposed to be done using FFT or not.
I think FFT can be done even with modulo 109 + 7. You can do it by FFT with some large two modulos, for example, modulo 1 + 7·226 and 1 + 5·225. Then you can restore the value using Chinese Remainder Theorem (or extended Euclidean algorithm). And finally modulo it by 109 + 7.
Obviously, this way also works for 109 + 9, 998244353, or some other modulos. But, if the modulo is 109 + 7, I think that some people may think "the solution is definitely not FFT" even if FFT is actually involved. Finally, I think taking modulo with 109 + 7 or 109 + 9 is the best way to hide the solution (whether FFT or not).
Recently, problem setters found that giving every problem modulo 998244353 is the best way to hide the solution :( Now 998244353 doesn't mean anything. There are so many problems not using FFT but having modulo 998244353...
Sorry, I wasn't necessarily talking about polynomial multiplication: I agree you can do CRT to do polynomial multiplication mod 109 + 7 say. 998244353 is special because you can actually do a fourier transform with a 2n-th root of unity.
Also, I would say that I also agree that it's just more convenient to have a template to do polynomial multiplication modulo p for any prime p.
desert97 Can you explain what you meant?
I wonder what people will do if I invent an algorithm which only works on mod 696969420...
People won't do this problem since they will get the ultimate orgasm with the first glance.
Just imagine what will happen if people realize there were already some good problems about mod 2!!
usernameson Did you find the reason?
I guess the reason to use 998244353 instead of 10**9+7 is that this hides the answer better... Can't seem to find anything else... This number has again been used in Educational Round 79 (1279D - Santa's Bot)
The FFT answer above made sense to me so I assumed it was correct.
I'm still waiting for 1000696969 to become a popular mod prime.
In china it's more commonly written as (119<<23)+1
Say my question asks mod 10^9 + 7 but I use 998244353 to take advance of the polynomial operations . Now how do I transform my answer back to modulo 10^9+7 ?