非想定解あるある、制約のせいで逆に迷った。 問題概要 atcoder.jp 考えたこと 今回は 1-indexed で考えた方が圧倒的にわかりやすいのでそのように統一する。 箱の色容量 色 $ i $ のボールを $ j $ 番目の箱に $ j $ 個入れる操作を「 $ 1 $ 色入れる」と定…

困ったときの平方分割。 問題概要 atcoder.jp 考えたこと 要素の総和が $ k $ の"素晴らしい整数列"の個数を $ f (k) $ とする。 また、このうち最後の要素が $ x $ であるものの個数を $ f _ x (k) $ とすると、 $$ f _ x (k + x) = f(k) - f _ x (k) $$ が…

問題概要 atcoder.jp 考えたこと なんとなく、親ノードに遡りながら状態をまとめていけばよさそう。 当初、特殊辺を二つの木に対して同時に親ノード側に伸張することを考えたが、二つの特殊辺が片方の木でのみ接続するパターンに対する数え上げパートが原因…