1樓：ghj1222
b乎莫名其妙給我推薦了一番，那我就來解釋一番
1e9+7這個數，滿足[0,1e9+7)內所有數，兩個數相加不爆int，兩個數相乘不爆long long
還有一點，由於1e9+7是質數，所以在[1,1e9+7)內所有數都存在關於1e9+7的逆元（這樣就可以做除法）
至於998244353，是個質數並且可以表示成a*2^b+1的形式，其中b大概為20多（？），假設我們有乙個原根g使得g^0,g^1,...,g^998244351取得所有[1,998244353)的數，由於b中有很多2的因子，這樣g^n可以代替單位根 ；由於fft需要下標為2的冪次的單位根，這樣代替使得n取得整數；從而進行數論上的fft(ntt)操作，這種數字一般會提示你這題要用ntt，類似的數字還有1004535809
然後vfk就說以後所有要取模的題就都寫***就好了（來迷惑選手），這個數也被稱為uoj素數。（其實不滿足這種a*2^b+1的也可以，參見任意模數NTT
然後這些數字由於很常用（包括某人的生日19****17），經常被毒瘤出題人卡雜湊，寫雜湊慎用
2樓：Super SASS
其他同學都已經說得很詳細了，這裡再弱弱地補充運算上的乙個小點【……【以下將對 取模記為 …… 】
對冪運算的指數取模，模數應該取。其中： 是尤拉函式[1]，表示的是小於等於 的範圍裡和 互質的數的個數……
很顯然：當 是質數的時候， ……如：當 時，計算 。
則結果為 。
若要對指數取模，應該為 【因為 是質數，所以】。然後 。
而不是 。
以上是根據費馬小定理x尤拉定理中的擴充套件尤拉定理[2]得來的……
當 或其他大質數時……
對冪運算的指數取模為： ……【質數的尤拉函式直接是原數-1，這也應該算是模數取為質數的原因之一吧
3樓：skito
在某些演算法題裡不要求解答者考慮程式中超出儲存範圍的數值該如何儲存，但使用的資料又可能會溢位，所以允許用ans%mod來代替ans。
作為mod的值有幾個要求：
mod要盡可能大，確保程式中可能的計算結果對該值取模後在資料型別的表示範圍內。例如，a和b都是32位int型別的值，（a+b）的值取模後要在32位int型別表示的範圍之內。如果mod值太小，比如極端點說，mod=1，則起不到足夠的將ans縮小的作用。
mod應該是乙個質數，防止ans取模後等於0。例如：（9*5）%15 = 0。
綜上可知要選擇乙個32int表示範圍內盡可能大的質數。1e9+7 = 1000000007 是32位int型資料能表示的範圍內較大的幾個質數之一。容易被記住也是使用該值的乙個原因。
根據以下性質，在程式中應該有選擇性地使用不同的表示式：
(a-b)%mod = ((a%mod) - (b%mod))%mod
(a+b)%mod = ((a%mod + (b%mod))%mod
(a*b)%mod = ((a%mod) * (b%mod))%mod
(a/b)%mod ≠ ((a%mod) / (b%mod))%mod
4樓：
1.這是乙個質數，mod出來的結果相對準確。
2.它小於INT_MAX(2147483647)，int型別能存下。就算是兩個(1e9+7)加起來也不會溢位。
3.簡單好記，不至於選手記錯數字。
4.這是合適範圍內最大又方便的的質數。
5樓：EntropyIncreaser
其實不止1e9+7，還有1e9+9和998244353。這三個數都是乙個質數，同時小於 。所以有什麼好處呢？
1. 所有模過之後的數在加法操作在int範圍內不會溢位，即 。
2. 在乘法操作後在long long範圍內不會溢位，即 。
3. 對於 中的整數，可進行mod P乘法群意義下的除法，即可以使用擴充套件歐幾里得演算法求得 中的a。
(另：其實也可以不mod乙個質數，那樣的話除法就複雜一些，需要進行素因子分解之後幫助除法和中國剩餘定理來還原最終答案。)
6樓：Manchery
很多回答都提到了取模既避免了高精度運算，又能保證極少的衝突情況，可以說如果在模意義下跟答案一樣，那麼就相信你得到了正確答案。
我來補充一下，可能偏題了。
100007不是乙個質數，然而***是乙個質數，取質數作為模數還有乙個好處是方便進行除法運算，也就是除了0都存在逆元。
7樓：楚子航
以下內容搬運自萌萌的程式媛
為什麼要對***取模 - 柳婼 の blog
為什麼要對***取模
大數階乘，大數的排列組合等，一般都要求將輸出結果對***取模為什麼總是***呢= =
大概是因為：（我猜的，不服你打我呀~）
1. 1000000007是乙個質數
2. int32位的最大值為2147483647，所以對於int32位來說***足夠大
3. int64位的最大值為2^63-1，對於***來說它的平方不會在int64中溢位
所以在大數相乘的時候，因為(ab)%c=((a%c)(b%c))%c，所以相乘時兩邊都對***取模，再儲存在int64裡面不會溢位
為什麼很多Linux軟體的安裝教程都要求關閉swap？
我自己一般是關掉，或者留2G 前提是有足夠的記憶體，和可以評估記憶體的用量 swap其實只能swap一下冷資料，如果真的是跑程式，機械硬碟會非常慢，SSD會磨損嚴重 真實環境是需要加記憶體 小比 沒聽過這種事情會強制 有幾種可能性，要嘛就是storage太小不夠空間，要嘛就是RAM太大不在乎。或是以...
為什麼RPG類遊戲很多都要求玩家刷怪練級刷裝備？
chen 之前已經有兩個公司為你打抱不平了，他們也是極度厭惡刷子遊戲。打遊戲嘛，就是要爽，就是要快！準！狠！這樣才過癮對吧。像個娘們一樣，打boss前還要刷刷刷，開什麼玩笑？然後 就沒有然後了。以至於說到遊戲主機陣營，就是索尼和任天堂出鏡率最高。誰還記得世嘉和微軟呢。修辭手法，勿槓 沒完呢，冤有頭債...
物理競賽題答案看的懂但是做不出來是為什麼？
whathow 沒有真正理解物理過程，對於題目的把握也不夠。看得懂和會不會做二者不是等價的，建議先把基礎打牢吧！多思考物理過程，多總結。推薦你去看 費曼物理學講義 可以提公升物理學素養 KMP7 如果題主是剛學，那很正常。剛看完競賽知識點是沒辦就迅速學會解題思維的。想要提公升自己能力最根本的應該是多...