ABC177C
from ABC177
ABC177C
全部出して二乗したものから、対角線を引いて、半分にする
「2で割る」を素朴に割り算切り捨てしててWA
奇数の場合にはMODを足して偶数にしてから2で割る
pythondef solve(N, AS):
sum = 0
sumSq = 0
for i in range(N):
sum += AS[i]
sum %= MOD
sumSq += AS[i] * AS[i]
sumSq %= MOD
ret = (sum * sum - sumSq) % MOD
if ret % 2 == 0:
return ret // 2
else:
return (ret + MOD) // 2公式解説は累積和だね、横一列を1回の掛け算で済ます方法
僕の解法は「単純に2で割れないから逆元を使った難しい解法になる」と言われてた
抽象的に考えすぎて難しいだけでは。
11ぐらいの小さい数で試したことがあれば難しくなく思いつけると思う
pythonxs = [None] * 11
for i in range(11):
xs[i * 2 % 11] = i
# xs => [0, 6, 1, 7, 2, 8, 3, 9, 4, 10, 5]こんな感じで2i番目にiが入ってる
奇数番目には一旦最後まで行ってから2周目に値が入る
うーん、最速には4ms及ばなかったか！
最速コードは剰余を最後にしか取らない
最大10^30程度なら長整数で押し切った方が速いのかー
Related Pages
- →数え上げ×degwer×状態をまとめる×dpは全探索の高速化×arc059f×codefestival_2016_final_f×aoj2439×探索順の変更×大きい順に並べる×aoj2333×順列は挿入dp×bit_dp×区間は終点でソート×条件の言い換え×操作は多いが産物は少ない×agc013d×線形和への分解×演算順序の変更×ビット演算を桁ごとに分解×部分群×操作が可逆で全域→部分群×ラグランジュの定理×再帰的定義→dp×arc037d×桁dp×aoj0570×累積和×フェニック木×高速フーリエ変換×ntt×高速ゼータ変換×and_と_add_の畳み込み×二分累乗×agc013e×行列木定理×全域木の個数×lgv公式×非交叉経路の個数×小さい確率を無視する×二項係数の公式×経路数×45度回転×xとyにわける×カタラン数×包除原理×agc005d×約数系包除×arc064f→
- →僕のatcoderの学び方(〜水色)×僕のatcoderの学び方(〜past上級)×abc187×past過去問練習202012×変形テクニックに名前をつける×頂点数18の制約×辺が10^5の制約×行列の半分×二項定理×足し算の順序の変更×辺が10^5ならダイクストラ使える×典型力×問題変換×問題分割×認知の解像度×概念のハンドル×atcoder失敗リスト×atcoderentrypoint×アルゴリズム実技検定×第五回_アルゴリズム実技検定×最小費用流に帰着×帰着訓練→
- →帰着する力×小さい制約の問題×nが8前後の制約×nが10~20前後の制約×n_が_30~40前後の制約×n_が_50前後の制約×n_が_300~500前後の制約×n_が_1000_前後の制約×小さな定数に注目×変数を一つ固定する×3つのものの真ん中を固定×行列の半分×xとyにわける×操作の不変量に注目×偶奇に注目×偶奇で場合わけ×操作の順番によらない×時間軸反転×元に戻せる操作×左右から累積積×等差数列の加算は差に注目×区間反転の合成はxor×grundy数×余事象を引く×k番目の数を二分探索×xorは繰り上がりのない足し算×xorは桁ごとに分割可能×45度回転×差の最小化は中央値×代表的なグラフで考察×木は二部グラフ×木の直径×最大化を二分探索で×選択肢が少ない方から貪欲×二次元座標を二部グラフにする×順序を有向グラフにする×凸関数の極値は三分探索×単調増加ならしゃくとり法×等比数列は剰余に注目×n進数は剰余に注目×括弧列は上り下り×競技プログラミングで解法を思いつくための典型的な考え方×keyence2020_d×abc152_f×agc026_c×arc060_a×joi2008ho_c×abc034d×abc138e×abc023d→
- →僕のatcoderの学び方(〜緑)×僕のatcoderの学び方(〜青)×ARC106×気づきの言語化×結晶化×変形テクニックに名前をつける×行列の半分×二項定理×足し算の順序の変更×概念のハンドル×テストできるスニペットライブラリ×unionfind×mod_pでの組み合わせ×educational_dp_contest×動的計画法×atcoder_library_practice_contest×AtCoder Library×帰着する力×帰着訓練→
- →atcoder×atcoder_library_practice_contest×numba×cython×フェニック木×セグメント木×遅延伝搬セグメント木×接尾辞配列×lcp_array×pythonでの累乗・逆数・階乗・階乗逆数・組み合わせ×中国剰余定理×floor_sum×np.convolve×two_snuke×長整数が速い×dsu×unionfind×最大流×最小費用流×scc×2-sat→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]