Atcoder ARC058E Iroha and Haiku
题目中的式子转化一下即存在一位 \(i\) 使得到 \(i\) 时的后缀和存在 \(X + Y + Z, Y + Z, Z\)，再发现 \(X + Y + Z\le 17\)，考虑状压。
设 \(f_{i, j}\) 为填了 \(i\) 个数当前后缀和中存在的数的状态为 \(j\)（只存 \(0\sim X + Y + Z\) 的数是否存在）的方案数。
考虑转移，则下一位可以填上 \(1\sim 10\) 的数，对应的后缀和就应左移对应位数同时 \(+1\) 代表存在后缀为 \(0\)，\(f_{i + 1, j\times 2^d + 1}\leftarrow f_{i + 1, j\times 2^d + 1} + f_{i, j}(1\le j\le 10)\)。
统计答案考虑若在第 \(i\) 个数满足条件就直接加上答案不继续往后转移，否则可能会算漏一部分。
当 \(j\) 对应的存在状态中已存在 \(X + Y + Z, Y + Z, Z\) 时，后面的 \(n - i\) 位就可以任意填了，对应的方案数就为 \(f_{i, j}\times 10^{n - i}\)，对所有满足条件的状态按照此式子求和即可。
时间复杂度 \(O(nW\times 2^{X + Y + Z})\)，\(W\) 为值域，此题为 \(10\)。