ABC194F
from ABC194
考えたこと
DP Sをコピペして書き換えた
サンプルは通ったんだけど遅い、TLEが解消しない
「16通りの数字が既に出てるかどうかを記録」で6万~になり2×10^5回更新するから厳しいよな
公式解説
僕は「何が既に出てるかわからないと、たとえば次に1が出た時に、出現済みの数字の個数が増えるのかどうかわからない」と考えた
それは真
だけど0〜Fの16通りを計算するのだから、どれが出現済みかわからなくても「16個のうちでいくつで出現済み個数が増えるか」はわかる
よって出現済みの数字の個数だけを保持すれば良い
コンテスト後AC
pydef solve(N, K):
MOD = 1_000_000_007
D = 16 + 1
less = [0] * D
equal_used = [0] * 16
equal = 0
for digit in N:
digit = int(digit, 16)
new_less = [0] * D
for d in range(D):
new_less[d] += less[d] * d
if d == 0:
new_less[d] += less[d] * 1
new_less[d + 1] += less[d] * 15
elif d != 16:
new_less[d + 1] += less[d] * (16 - d)
for new_digit in range(16):
if new_digit < digit:
new_d = equal
if equal_used[new_digit] == 0:
new_d += 1
if new_digit == 0 and equal == 0:
new_d = 0
new_less[new_d] += 1
for d in range(D):
new_less[d] %= MOD
less = new_less
if equal_used[digit] == 0:
equal += 1
equal_used[digit] = 1
ret = less[K]
if equal == K:
ret += 1
return ret % MODRelated Pages
- →数え上げ×degwer×状態をまとめる×dpは全探索の高速化×arc059f×codefestival_2016_final_f×aoj2439×探索順の変更×大きい順に並べる×aoj2333×順列は挿入dp×bit_dp×区間は終点でソート×条件の言い換え×操作は多いが産物は少ない×agc013d×線形和への分解×演算順序の変更×ビット演算を桁ごとに分解×部分群×操作が可逆で全域→部分群×ラグランジュの定理×再帰的定義→dp×arc037d×桁DP×aoj0570×累積和×フェニック木×高速フーリエ変換×ntt×高速ゼータ変換×and_と_add_の畳み込み×二分累乗×agc013e×行列木定理×全域木の個数×lgv公式×非交叉経路の個数×小さい確率を無視する×二項係数の公式×経路数×45度回転×xとyにわける×カタラン数×包除原理×agc005d×約数系包除×arc064f→
- →動的計画法×dp_a×dp_b×dp_c×dp_d×dp_e×dp_f×dp_g×dp_h×dp_i×dp_j×dp_k×dp_l×dp_m×dp_n×dp_o×dp_p×dp_q×dp_r×DP S×dp_t×dp_u×dp_v×dp_w×dp_x×dp_y×dp_z→
"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]