最近ABC-Dがむずい。
問題文が桁DPの形をしている。
k が 0~K の範囲を取るので一見計算量的に無理そうだが、 実際は1桁の数の積なので素因数分解すると 2a3b5c7d と表せる数に限られる。 a=0~log2K,b=0~log3K,... の範囲を取るので、多く見積もっても O((logK)4) で収まる。
これとは別に「just: N の上位 i 桁目までの積」も管理しておけば、更新は以下の3つで行える。
上位 i−1 桁までの積が m の時、i 桁目を t=0~9 のいずれにするかで10通りに遷移する。
DPに新しく追加される。
N の i 桁目が x の時、 DPで管理する数の i 桁目は t=0~(x−1) にすることができる。
上記と同様に遷移する。ただし新規に追加されるパターン数は1通りとなる。
DPに新しく追加される。
i≥2 において、t=1~9 の9通りに遷移する。
途中でansに加えられた数と、DPで管理されている数をあわせたものが答え。
ただし、N そのものが各桁の積が K 以下である場合は数えられていないので、 just≤K であれば答えに1足す。
10進数なので各状態からの遷移は D=10 通り ずつあり、計算量は O(logN(logK)4D) となる。
定数 INF を K より大きい数(何でもよい)として定義しておく。
mk>K となった場合、遷移先は DP[i][INF]+=DP[i−1][m] として1つの状態にまとめてしまえばよい。
この方法なら f(i) を考える必要が無いため、追加実装が少なく抑えられる。
制約が N,M,K で意味ありげに異なっていて、特に M が小さい。
問題ページのサンプル1の説明にも表があるが、 n \gt 0, m \gt 0 の部分に関しては、よくある経路数え上げのように「上と左の値を足す」という操作になっている。
で、左端が n^K、上端が 0 で初期化される感じ。
K=2 n\m 0 1 2 3 4 0 0 0 0 0 0 1 1 1 1 1 1 2 4 5 6 7 8 3 9 14 20 27 35
左端が特殊なものの、遷移は経路数え上げなので、二項係数が出てきそう。
左端の値毎に表を分離すると以下のようになり、
それぞれの表は二項係数の表(をシフトしたもの)に [ ]
でくくった数をかけたものとなっている。
n\m 0 1 2 3 4 0 0 0 0 0 0 1 [1] 1 1 1 1 2 0 1 2 3 4 3 0 1 3 6 10 n\m 0 1 2 3 4 0 0 0 0 0 0 1 0 0 0 0 0 2 [4] 4 4 4 4 3 0 4 8 12 16 n\m 0 1 2 3 4 0 0 0 0 0 0 1 0 0 0 0 0 2 0 0 0 0 0 3 [9] 9 9 9 9
f(n,m) はその総和なので、以下で表せる。
……が、N が巨大すぎてこんなんまともに計算できない。どうすんの?
知識ゲー的なところはあるが。
x の D 次多項式 f(x) は、D+1 個のサンプル点 (x_i, f(x_i)) を与えることで一意に決まる。
それを利用して、f の形を機械的に特定し、 他の x を代入しても答えを求められるようにするアルゴリズムが、ラグランジュ補間になる。
先ほどの f(n,m) は、m=M を固定すると n の多項式として表せる。
まずΣの中の部分は、i^K はそのまま i の K 次式、 {}_{n-i+M-1}C_{M-1} は展開すると i の M-1 次式になるので、 あわせて K+M-1 次式となっている。
それの和を1から n まで取ると、次数は1個増えて n の K+M 次式となることが証明されている。
従って、K+M+1 個の n に対する f(n,M) を愚直に計算して、ラグランジュ補間すれば答えが求まる。
この時、一般的にラグランジュ補間は O(D^2) かかってしまうが、 サンプル点の n を適切に選ぶ(0~K+M の連番にする)ことで、 1つの値を求めるだけなら O(D) で計算できるテクニックがあるので、それを使う。