ARC 058 E - 和風いろはちゃん / Iroha and Haiku

• 問題

問題概要

整数N,X,Y,Zが与えられる.
整数1〜10から成り,XYZを含む要素数Nの数列をmod1e9+7で求めよ.
なお{a_i}がXYZを含むとは
sum(x<=i<y)(a_i) = X, sum(y<=i<z)(a_i) = Y, sum_(z<=i<w)(a_i) = Z
を満たす 0 <= x < y < z < w <= N が存在することとする.
1 <= N <= 40, 1 <= X,Z <= 7, 1 <= Y <= 5

解法

数え上げDP.
数列{a}に対し全単射の写像f({a})が存在すれば,各0<=i<N,f({a}),1<=k<=10に対し
dp[i+1][f({a}+{k})] += dp[f({a})] とすると, O(10N * size(f)) で求められる.

問題はこの写像をどう定義するか. 単に数列を並べたもの,もしくは数列自体にするとsize(f)=10^Nとなりとても終わらない.
この問題だと末尾から和がX+Y+Z-1以下になるような部分だけを覚えておけばいいことがわかる.
ex. X,Y,Z = 5,7,5 , {a} ={1,3,4,4,1,1,6,2}だと {4,1,1,6,2} の部分.
これは 1 = 1, 2 = 10, 3 = 100,..とすればうまくいく.
ex. f({1,2,3}) = 110100となる
X+Y+Z-1以下だけ見ていけば良いので, size(f) = 2^X+Y+Z-1 になる.
下からX+Y+Z,Y+Z,Zのビットが立っているようなものがXYZを含む数列になるので,
そのようなものを数え上げる.(コードだとjインデックスの最後に置いている)
この写像の立て方をしなくても,このような数列に対しインデックスをつけて下処理すればできるっぽい kmjpさんのブログ

メモ

和の通り数をコンビネーションで解こうとして無理だった.
(数え上げDPの典型処理ができなかった.)

コード