Dまで四完。ARCの後だったこともあり、前半は休み休みやっていた。
コンテスト後のツイート
D A[i]の最上位bitがbだとすると、l～i+1の累積xorでbが立っている/立っていない個数、i+1～rの累積xorでbが立っている/立っていない個数を調べて、l～rの累積xorではbが立っていないような個数を掛け算して求める。方針が立ってから、添え字とかで非常に苦労した。
— titia (@titia_til) April 21, 2024
E. Carousel of Combinations
解説AC。
Combi(n, k)*(k-1)! mod k の和を求める問題。実験コードを書いてこれを計算してみると、k=4と素数のとき以外は0になること、かつ、規則的に値が変化することが分かる。ｋを固定したとき、最初に値が正になるのはn=kのときで、k-1。そこからkごとに-1し、0になったらまたk-1に戻る。（これはkが素数のとき。k=4は2と0を交互に取る）
これが分かった後、埋め込みか？ などと考えてしまい解説を見てしまったが、累積和を二回やるのが正しかった。規則的に値が変化するのだから、累積和を考えるのは自然。
大体解けたけどTLEが微妙ってとき、変な手法を考えてしまうのは悪い癖。まともに計算量を減らす手法を考えるようにしないといけない。
0 件のコメント:
コメントを投稿