xor sum 4 - abc 147 d

解法

(xorの和)
= (桁上がりを無視した足し算の和)
= (足し算の和) - (桁上がりの和)

10^9+7で割るとこで事故った

waのコード
Submission #8867231 - AtCoder Beginner Contest 147
まず, 41行目あたりでAがlong longでもギリギリなことに注意

(1)59行目

(ans += P[i + 1] * (table[i] * (table[i] - 1) / 2) % inf) %= inf;

(2)

(ans += P[i] * table[i] * (table[i] - 1)) %= inf;

でもダメ
そうか, tableに3 * 10^5くらい入りうる

(3)

(ans += P[i + 1] * table[i] % inf * (table[i] - 1) / 2) %= inf;

でもダメ
割り算ダメか

(4)

(ans += P[i] * table[i] % inf * (table[i] - 1)) %= inf;

でok

(3)において
Submission #8884551 - AtCoder Beginner Contest 147
割り算を掛け算に直した

フェルマーの小定理より,
p : 素数, p !| a ∈ Zに対し,

よって, aの逆元は
aで割る代わりにをかける

(5)
modint構造体を使う
Submission #8884845 - AtCoder Beginner Contest 147

tweet