k-bonacci 数列の母関数

k-bonacci 数列の母関数, ぱっと頭に思い浮かびますか？ 僕は思い浮かびませんでした

ということで頑張って求めてみます



数列 a _ 0, a _ 1, a _ 2, \ldots について

 \begin{aligned}
a _ n =
  \begin{cases}
    1 &(0 \le n < k) \cr
    \displaystyle\sum _ {i = 1} ^ k a _ {n - i} &(k \le n)
  \end{cases}
\end{aligned}

とする

この数列の母関数 f(x) を

 \begin{aligned}
  f(x) =  \displaystyle\sum _ {n = 0} ^ \infty a _ n x^n
\end{aligned}

として, 閉形式を考える

 \begin{aligned}
  f(x) &=  \displaystyle\sum _ {n = 0} ^ \infty a _ n x^n \cr
  &= \displaystyle\sum _ {n = 0} ^ {k-1} a _ n x^n + \displaystyle\sum _ {n = k} ^ \infty a _ n x^n \cr
  &= \displaystyle\sum _ {n = 0} ^ {k-1} x^n + \displaystyle\sum _ {n = k} ^ \infty a _ n x^n \cr
  &= \displaystyle\sum _ {n = 0} ^ {k-1} x^n + \displaystyle\sum _ {n = k} ^ \infty \left( \displaystyle\sum _ {i = 1} ^ k a _ {n - i} \right) x^n \cr
  &= \displaystyle\sum _ {n = 0} ^ {k-1} x^n + \displaystyle\sum _ {i = 1} ^ k \left( \displaystyle\sum _ {n = k} ^ \infty a _ {n - i}x^n \right)  \cr
  &= \displaystyle\sum _ {n = 0} ^ {k-1} x^n + \displaystyle\sum _ {i = 1} ^ k \left( \displaystyle\sum _ {n = k} ^ \infty a _ {n - i}x^{n-i} \right)x^i  \cr
  &= \displaystyle\sum _ {n = 0} ^ {k-1} x^n + \displaystyle\sum _ {i = 1} ^ k \left( \displaystyle\sum _ {n = i} ^ \infty a _ {n - i}x^{n-i} - \displaystyle\sum _ {n = 0} ^ {k - i - 1} a _ n x^n \right)x^i  \cr
  &= \displaystyle\sum _ {n = 0} ^ {k-1} x^n + \displaystyle\sum _ {i = 1} ^ k \left( f(x) - \displaystyle\sum _ {n = 0} ^ {k - i - 1} x^n \right)x^i  \cr
\end{aligned}

f(x) を移項して

 \begin{aligned}
  f(x) - \displaystyle\sum _ {n = 1} ^ k f(x)x^n &= \displaystyle\sum _ {n = 0} ^ {k-1} x^n - \displaystyle\sum _ {i = 1} ^ k \left(\displaystyle\sum _ {n = 0} ^ {k - i - 1} x^n \right)x^i \cr
  &= \displaystyle\sum _ {n = 0} ^ {k-1} x^n - \displaystyle\sum _ {i = 1} ^ k \left(\displaystyle\sum _ {n = i} ^ {k - 1} x^{n} \right) \cr
  &= \displaystyle\sum _ {n = 0} ^ {k-1} x^n - \displaystyle\sum _ {n = 1} ^ {k - 1} nx^n \cr
  &= 1 - \displaystyle\sum _ {n = 1} ^ {k - 1} (n - 1)x^n \cr
\end{aligned}

両辺割れば

 \begin{aligned}
  f(x) = \dfrac{1 - \displaystyle\sum _ {n = 1} ^ {k - 1} (n - 1)x^n}{1 - \displaystyle\sum _ {n = 1} ^ k x^n}
\end{aligned}

最初のほうを 0 にすれば分母がもっときれいになるけどまぁ

歳をとりました

らしい



大学に入ってからというもの, 自分の歳や誕生日というものを全然意識しなくなってしまった

自分が今何歳なのかは覚えていないし, 今日誕生日だったなということをTwitterの風船で気づいた

そもそも時期的に人と会わないしね

いろいろと変わる年になるけど, 生き残れたらいいね

文字列に含まれる回文の種類数は高々 |S| 種類

はじめに

長さ N の文字列 S を考えます

S の空でない部分文字列 (N(N - 1)/2 通りあります) のうち, 回文であるようなものは高々 N 種類しか存在しない

らしいです

N を達成するのは簡単で, 全部違う文字にすればいいです

けどここから増やす方法は存在しないのでしょうか？

なかなかに非直感的に感じたのでちゃんと考えてみましょう

本文

帰納的に示すのがよさげです

文字列 S が存在していて, S の末尾に文字 c を一文字追加するときのことを考えます

この時, S に含まれる回文の種類数は高々 1 種類しか増えないことが言えます

さて, このときの回文の増え方として c が回文の右端になる という場合のみ考えればいいことがわかります

そのような回文のうち, 最も直径が長いものを T, そうでないもののうちの一つを U とすると, T, U は回文なので T に U が二つ以上含まれることがわかります (右端に合わせるか左端に合わせるか)

よって, T 以外の回文はすべて S にすでに存在していたことになります

したがって, S の長さが 1 増えるたび回文は高々 1 種類しか増えないことがわかります

以上より, S の空でない部分文字列のうち, 回文であるようなものは高々 |S| 種類しか存在しないことがわかりました

おわりに

こう考えるとわりと単純 けどぱっとは思いつかなくない？

と思い記事を書いてみました

回文に関するデ/アといえばみんな大好き Manacher's algorithm のほかに Palindromic Tree というものがあるらしいですね 勉強しないとな

ICPC2022アジア地区参加記

でたよ

0日目

宿の手配とかは全部やってもらってたので何もしていなかったが, そういえば検索ができないことを思い出したのでICPC用のライブラリを作ることにした 遅延セグ木とかFFTとかそういうのを短めにしたやつを印刷した 荷物を準備して寝る… と見せかけて RiJ を見ていた

1日目

あさ

神奈川県の行脚を付けてなかったのでちょっと早めに行ってゲーセンを探すことにした

（ここで大ミスをしたのだが, 横浜駅で降りてやってから会場に行けばよかったのに日本大通りに行ってから探してしまった あの辺全然ない）

GIGOにげきちゅうまいちょうど1台ずつ置いてあったのでそこで行脚を回収した

ひる

コーチの人に初めて会った(いい人でした) 受付からいきなり英語で心が折れた

リハーサルが始まったが, りなっくすなにもしらんの民なのでこまった セッティングとかだいたいやってもらった 前日に読んだ過去の出てた人の参加記を思い出すと, コンパイルオプションを alias すると嬉しそうだということに気づいた snuke さんが確か g++ を c++17 とかを付けたやつにしていたのでそれをやってみた

TLE OLE などを A問題で一通り試してからAC, Bのインタラクティブをチームメイトにやってもらいながら Cをチラ見すると知ってる過去問そのままだったのでスルーしてDを考える

平行な直線を何本作れますか？ だと誤読して bitDP したがサンプル3が合わず, 直線のペアを数えるのだと気づいた (英語が読めないのでサンプルと画像からエスパーしています)

誤読のときの bitDP を再利用して, それをした後に 部分集合を 3n でやるやつでもう1回 DP してみた 問題も正当性も計算量も何も分かってなかったがなんか AC がでたのでおっけー

Cはチームメイトに託したがそのまま時間切れになったのでリハーサルは終わりになった

よる

チームメイトと中華街に行ってみた コーチがいろいろ調べてくれていたらしく, おすすめされたお店に行ってみた おいしかったです

朝電車で暇だったので Library Checker の Convex Layers を考えていたのだが, 完全に理解したつもりになったので RiJ をみながら実装していた (めちゃくちゃ思考がハム太郎に持ってかれた)

バグる気しかしなかったので assert を入れまくったのだが, ランダムケースだけ見事に全部落ちて発狂した

Monsterの残りを飲んだり鼻血が出たりして全然寝れなかった

2日目

あさ

早めに起きて Convex Layers のデバッグをした 勘違い気づいて色々直した結果, 1ケースだけWA になってあと全部 AC になった でかいランダムケースぽくて原因が全然わからなくてつらい

時間がやばいのでチームメイトをさそって朝ごはんを食べた

ついでにいくつかライブラリを追加で印刷して register

ひる

ついに本番！ 体調もメンタルも最悪だが頑張る

例の如くセッティングしてもらいながら A を読むとよくある区間スケジューリング的なあれだった 制約も優しいので適当に書いてAC

風船が貰えないのが残念すぎる 自分で膨らませようかと思ったがさすがに自重した

その間にBを読解してくれていた なんかインタラクティブだけど桁ごとににぶたんすれば良さそう 流れで書いてAC

Cがよく分からんので全体的に見てみると, 全体的によくわからない

EFG辺りがなんだか解かせる気がありそうな見た目をしているのでいろいろ考えてみる

Gは追加する辺を全部試せばいいんじゃないかと気づいた 1本追加してなもりグラフになるので適当な辺を切る事でその閉路を解消できる

元々の最短経路から生えている木同士から2点選ぶとだるいことになりそうなので弾くためにだるい思考に入ってしまった

さすがに LCA とか取りたくなかったので, 最短経路を復元→そこから生えてるやつをdfs→ufでマージ とすることにした (uf要らなくね？)

とりあえず書いてみてサンプルが合ったので提出したがWA, いろいろ考えるとなんか根元といい感じにループになっちゃうときに変な値になるコードを書いてしまっていたことに気づき, グリッドグラフなことを利用した手抜きデバッグで直した AC

この時点でなんか13位くらいにいた びっくり

この後がつらくて, 順位表を見てFに飛びついてしまった なんか2次元スーパー部分和DP的なことをすれば良さそうに見えたが計算量が頭悪い

縦も横も同じだし実は1次元で2通り作れたらいい感じに組み合わせて Yes になるんじゃない？w とか笑ってた

実はエスパーの天才だったらしくこれ正解なのですが, 結局書かなかった アホ

あとなんかコイン移すやつを Zobrist hash 的なアレで上手くいかないかなって考えて一生ハマってた 終了10分前に想定解に気づいたが実装が間に合わなかった

あとなんか ICPCなんちゃらsubstring の問題がめちゃくちゃ好みな設定だったのに全然解けなくて悲しかった 迷走して, NTT mod なせいで3次元FFTとかするのかなとか考えていた

こんな感じでだいたい終わった

幾何とか読んでなかったけどおもしろそうなので後で解きたいな

あとなんで構文解析無いんですか

よる

もうヘトヘトでフォロワー探しの旅に出る元気がなかった とがさんはなんかいい感じに挨拶できてよかった

そういえば手元動画を撮らないと行けなかったことを思い出してゲーセンに行って弐寺を2クレだけやった 頻度減らしすぎて地力が狭義単調減少 つらい

次の電車を逃したらバスがなくなって1時間くらい歩く羽目になることに気づき, めっちゃ急いで電車に乗り込んだ

めっちゃ人いて, つらい…

家が遠すぎます

おわりに

最初で最後のアジア地区予選, あと多分最初で最後のオンサイトコンテストということで, いい経験になりました

楽しくもあり辛くもあったけど, やれてよかったと思います

ABC281 - Ex を非再帰で書いた

タイトルのままです 再帰アレルギーの方のために

じゃなくて普通にこっち先に思い付いた

方針は公式解説と同じです 別にそんな速くはなさそう

二冪の prefix にFFT のマージテクでできたやつかけていけばいいよねってだけ

自分の NTT でやったら 661ms で ACL だと 457 ms で悲しくなりました 書き直したいです


コード

#include <bits/stdc++.h>
#include <atcoder/convolution>
#include <atcoder/modint>

using namespace std;
using namespace atcoder;

using mint = modint998244353;
constexpr int mod = 998244353;

int p2(int n){
  while(n & (n - 1)) ++n;
  return n;
}

vector<mint> pre(const vector<mint> &a, int n){
  return {begin(a), begin(a) + n};
}

int main() {
  int n, a; cin >> n >> a;

  if(n == 1){
    cout << a % mod << "\n";
    return 0;
  }

  vector<mint> c(n + 1, 1), inv(n + 1, 1);

  for(int i = 2; i <= n; ++i) inv[i] = -inv[mod % i] * (mod / i);

  for(int i = 0; i < n; ++i) c[i + 1] = c[i] * (a - i) * inv[i + 1];

  c.erase(begin(c), begin(c) + 2);
  c.resize(p2(c.size()));

  stack<vector<mint>> sf, sa; sf.push(c);

  for(int i = 0; i < n - 1; ++i){
    vector<mint> f = sf.top();
    while(int(f.size()) > 1){
      sf.push(f = pre(f, f.size() / 2));
    }

    mint x = sf.top()[0]; sf.pop();

    if(i == n - 2){
      cout << x.val() << "\n";
      return 0;
    }
    
    f = {1, x};
    while(!sa.empty()){
      vector<mint> g = sa.top();
      if(f.size() != g.size()) break;
      sa.pop();
      f = convolution(f, g);
    }
    sa.push(f);

    int m = int(sf.top().size());
    f = convolution(f, sf.top()); sf.pop();
    f = pre(f, m);
    sf.emplace(begin(f) + (m/2), end(f));
  }
}

提出結果

atcoder.jp

あほこらを理解した

メモ書き

普通に Trie 生やしたあと今見てるノードの表す文字列の suffix のうち辞書の文字列の prefix として存在するようなものの中で最も長いものに link を繋ぐ

というのは知っていたが, なぜこれで上手くいくのかさっぱりわかっていなかった

例えば辞書が abcd, b, bce で見たい文字列が abce だったら abc まで行ったらつぎに bc のところに飛ぶのはわかるがそうすると b をスルーしないか？ と思っていた

これの対処法は, ab まで見たときにもう b をチェックすることになる

どうすればいいのかというと, 各ノードについて, suffix link の先のものもそこにあったことにすればいい

つまり, suffix link を構築するときに辞書に対応するノードにマークをつけておくが, そのノードの suffix link の先のマークも書き加える

そうすれば, 今のノードの文字列の suffix に対応する部分も全て拾える 頭がいい

構築は 0 から bfs をしていって, 自分の suffix link の次は 自分の次の suffix link ですみたいに埋めていけばいい

これだけなので実装はとても軽くて, Trie を書くところから始めてもそんなにかからなかった

区間に漸化式で表される数列を足すタイプの imos法

No.1172 Add Recursive Sequence - yukicoder

この問題のことです

頭が悪くて解説がすぐには理解できなかったので整理用にメモ

めんどうなので a, c は 0-based-index, c は反転して考えます

[l, r) に足す

というのを

[l, n) に a _ 0, a _ 1, \ldots, a _ {n - l - 1} を足して

[r, n) から a _ {r - l}, \ldots, a _ {n - l - 1} を引く

と考えると

[i, n) に a _ j, a _ {j + 1}, \ldots の定数倍を足すことを考えればいいです

足される数列を左から見ていきます

ほんとに [i, n) に足したら O(N) かかってしまうので, とりあえず x _ i にだけ足すことにします

x _ i に対して足すクエリをすべて処理した後の x _ i が

x _ i = \displaystyle\sum _ {j \in Q} p _ j a _ j

みたいにかけたとします ( p はいい感じの定数倍)

ここから

\displaystyle\sum _ {j \in Q} p _ j a _ {j + 1}

を求めることができれば, またクエリの左端が i + 1 であるようなものについてだけ足すことで x _ {i + 1} を求めることができます

ここで, 0 \le i \lt K について

y _ i = \displaystyle\sum _ {j \in Q} p _ j a _ {j + i}

という数列を考えてみます ( x _ i = y _ 0)

ここから

y _ K = \displaystyle\sum _ {j \in Q} p _ j a _ {j + K}

を求めることはできるでしょうか？

線形性があるので

y _ K = \displaystyle\sum _ {i = 0} ^ {K - 1} c _ i y _ i

と書けます (適当に代入してまとめれば出ます)

ということで, (y _ 0, \ldots, y _ {K - 1}) を持ちながらクエリを左から足していけば求まります

y を K 項常に持っているので, クエリでも K 箇所に足すことになります

これは a を N + K - 1 項目まで前計算しておけば O(K) で簡単に処理できます

y の遷移も O(K) でできるので, 全体で O((N + M)K) ですべてのクエリを処理することができます

実装 (せっかくなので雑に構造体にしてみた)

#796623 (C++17) No.1172 Add Recursive Sequence - yukicoder