e417.
乘法~乘法~加法~
--
π
| From: [203.64.161.123] |
發表日期
:
2020-03-04 11:59
本題十分的簡單，可以視為集合 U={1,2,...,N} 與集合 V={1,2,...,N} 的笛卡爾積，扣除掉集合 S={{1,1},{2,2},...,{N,N}}。
不妨考慮快速傅立葉轉換，將集合 U 視為一個 N-order 循環群，以循環群 U 代替本原根，並且將集合 S 代入快速富麗業轉換。
對於傅立葉轉換出來的結果，將所有數字加起來即可。
如果數字過大，可以取模雜湊，最後再用中國剩餘定理重組回來。