ABC249E - RLE

EDPC - M - Candies - 競プロはじめましたの類題だが，今回の方がはるかに難しい．．．

配るDP & いもす法

文字数が少ない問題に帰着させられそうなので，dpを考える．

「dp[i][j]=圧縮前の長さが$i$・圧縮後の長さが$j$の個数」としてみる．

文字を1コ追加させた遷移を考えると，末尾の文字とその個数によって遷移が変わってうまく行かない．そこで，末尾の文字とは異なる文字を$k$コ追加する遷移を考える．配るDPは

N, P = map(int, input().split())

dp = [[0] * (N + 1) for _ in range(N + 1)]
dp[0][0] = 1

for i in range(N):
    for j in range(N + 1):
        for k in range(1, N + 1):
            if i + k > N:
                continue
            if j + 1 + len(str(k)) > N:
                continue
            if i == 0:
                dp[i + k][j + 1 + len(str(k))] += 26 * dp[i][j]
            else:
                dp[i + k][j + 1 + len(str(k))] += 25 * dp[i][j]
            dp[i + k][j + 1 + len(str(k))] %= P

print(sum(dp[N][:N]) % P)

となり，3重ループで間に合わない．

しかし，$k$の桁ごとに見れば，「ある区間への遷移」になっているから，いもす法が使える形である（【参考】EDPC - M - Candies - 競プロはじめました）から，高速化できる．

iとjを逆にしたほうが見やすいが，上との整合を保つため，そのままで実装する．$i$からの遷移が終わったら，$i + 1$は確定させて良いので，累積和を計算する．

N, P = map(int, input().split())

dp = [[0] * (N + 1) for _ in range(N + 1)]
dp[0][0] = 1

for j in range(N):
    for i in range(N + 1):
        c = 26 if i == 0 else 25
        for k in range(1, 5):
            if j + 1 + k > N:
                continue
            if i + 10 ** (k - 1) <= N:
                dp[i + 10 ** (k - 1)][j + 1 + k] += c * dp[i][j]
                dp[i + 10 ** (k - 1)][j + 1 + k] %= P
            if i + 10 ** k <= N:
                dp[i + 10 ** k][j + 1 + k] -= c * dp[i][j]
                dp[i + 10 ** k][j + 1 + k] %= P
    for i in range(N):
        dp[i + 1][j + 1] += dp[i][j + 1]
        dp[i + 1][j + 1] %= P

ans = 0
for j in range(N):
    ans += dp[N][j]
    ans %= P
print(ans)

貰うDP & 累積和

また，貰うDPを考えると

N, P = map(int, input().split())

dp = [[0] * (N + 1) for _ in range(N + 1)]
dp[0][0] = 1

for i in range(1, N + 1):
    for j in range(N + 1):
        for k in range(1, N + 1):
            if i - k < 0:
                continue
            if j - 1 - len(str(k)) < 0:
                continue
            if i - k == 0:
                dp[i][j] += 26 * dp[i - k][j - 1 - len(str(k))]
            else:
                dp[i][j] += 25 * dp[i - k][j - 1 - len(str(k))]
            dp[i][j] %= P

print(sum(dp[N][:N]) % P)

となり，区間からの遷移になっているから，dp[i]を累積和で求めておけば計算量を落とすことができる（【参考】EDPC - M - Candies - 競プロはじめました）．ただし，累積和をとることでまとめて遷移できるのは，$k$の桁が同じもののまとまりである．

※実装しようとしたが，バグがとれなかった．そのうち再チャレンジしたい．