Yet Another 042

まず、ある数が $11$ の倍数であることと「奇数番目の桁の総和を $11$ で割った余りと偶数番目の桁の総和を $11$ で割った余りが等しい」ことは同値です。

ここで、次のようなDPを考えます。

• $DP[i][j][k]:=$ 現在の桁の総和が $i$ であり、奇数番目の桁の総和から偶数番目の桁の総和を引いた数を $11$ で割った余りが $j$ であり、現在の桁数の偶奇が $k$ である数の個数

このようなDPをすることで、遷移で $j$ に足すべきか引くべきかがわかるようになり、 $Ο(K)$ で解くことができました。