NF杯2024(M)

点数: 300

Writer: ipha

　$999×999$ のマス目があります．いくつかのマスに $1$ 以上 $999$ 以下の整数を $1$ つずつ書き込む方法であって，以下の条件をともに満たすようなものを輝く書き込みと呼びます．

• どの行，列についても，書き込まれる数字はちょうど $1$ つである．
• $i=1,2,\dots,999$ について， $i$ は $i$ 行目または $i$ 列目のマスに書き込まれている．

輝く書き込みにおいて，$i$ が $i$ 行 $i$ 列目のマスに書き込まれているような $1$ 以上 $999$ 以下の整数 $i$ の個数を $n$ とするとき，この書き込み方の輝度を $2^n$ によって定めます．このとき，すべての輝く書き込みに対し，その輝度を足し合わせた総和が $5$ で割り切れる最大の回数を求めてください．