【今日の精進】ABC235F - Variety of Digits

毎日格上の問題を倒すやつの79日目です。

問題リンク

atcoder.jp

問題概要

以下の整数であって、すべての を含むものの総和を求めてね。

解法

いわゆる桁DPです。

個の情報を持ち、それぞれに総和と個数を持っておきます。*1

時間が厳しそうな気持ちになりますが、祈れば案外間に合います。

提出コード

MOD=998244353
N=input()
M=int(input())
C=list(map(int,input().split()))
dp=[[(0,0)]*(1<<10),[(0,0)]*(1<<10)]
dp[0][0]=(0,1)
for i in N:
    i=int(i)
    aft=[[(0,0)]*(1<<10),[(0,0)]*(1<<10)]
    for j in range(1<<10):
        for k in range(i):
            if j==k==0:
                aft[1][j]=(aft[1][j][0]+dp[0][j][0]*10+k*dp[0][j][1],aft[1][j][1]+dp[0][j][1])
            else:
                aft[1][j|(1<<k)]=(aft[1][j|(1<<k)][0]+dp[0][j][0]*10+k*dp[0][j][1],aft[1][j|(1<<k)][1]+dp[0][j][1])
        if j==i==0:
            aft[0][j]=(aft[0][j][0]+dp[0][j][0]*10+i*dp[0][j][1],aft[0][j][1]+dp[0][j][1])
        else:
            aft[0][j|(1<<i)]=(aft[0][j|(1<<i)][0]+dp[0][j][0]*10+i*dp[0][j][1],aft[0][j|(1<<i)][1]+dp[0][j][1])
        for k in range(10):
            if j==k==0:
                aft[1][j]=(aft[1][j][0]+dp[1][j][0]*10+k*dp[1][j][1],aft[1][j][1]+dp[1][j][1])
            else:
                aft[1][j|(1<<k)]=(aft[1][j|(1<<k)][0]+dp[1][j][0]*10+k*dp[1][j][1],aft[1][j|(1<<k)][1]+dp[1][j][1])
        aft[1][j]=(aft[1][j][0]%MOD,aft[1][j][1]%MOD)
        aft[0][j]=(aft[0][j][0]%MOD,aft[0][j][1]%MOD)
    dp=aft
num=sum([1<<i for i in C])
ans=0
for i in range(1<<10):
    if i&num==num:
        ans+=dp[0][i][0]+dp[1][i][0]
print(ans%MOD)

atcoder.jp

感想

思ってたよりめっちゃ典型

*1:個数がないと総和を正しく計算できない