AGC019B
考えたこと
長さの偶奇で分けて考えるべきかな？
中心を固定して広げていくと、新しく範囲に入る文字が異なってれば2倍、異なってなければ1倍かな
それでも全然効率よくないね
20万文字あるのに「余りを答えよ」ではないのが不思議
範囲を定義域にするDPか？
ある2ペアの文字が異なってる場合、そのペアの交換を含む範囲は全部場合の数を+1する
はっ、包除原理か？
いや、対称性で絞れないから違うか
公式解説
異なる2種の文字を両端として作られる文字列は、互いに一致することがない
これに気づけば余事象を引くで「一致するペアの数を数える」に変わる
これは頻度→三角数で求まる
問題分割
Related Pages
- →帰着する力×小さい制約の問題×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→
- →地図読み込み時に番兵をつける×数列を有理式にする×ラグランジュ補間×対称性で次元削減×余事象を引く×未ac×足し算の順序を変える×xごとのf(x,y)の和はyごとのf(x,y)の和×最大値の期待値×順位統計量×maxの不等号は不等号のand×0,1→
"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]