AtCoder Regular Contest 136 D問題 Without Carry
問題
提出解答
問題の概要
長さ の列
が与えられる. 以下を満たす
以上
以下の組
の個数を求めよ.
を筆算で計算すると, 繰り上がりが発生しない.
制約
解法1 (条件)
とする.
以上
以下の整数からなる列の集合を
とする. このとき,
と
の間には
という対応がある. 以降ではこの対応による同一視を行うことがある.
また, に対して,
を
とする.
このとき, において,
を筆算で求める際に繰り上がりが生じないことと,
*1 であることは同値である.
解法2 (計上)
において,
となる
の個数を
とする. このとき, 求めるべき答えは
最後に, を求める方法を考える.
は直積順序であり,
である. よって,
次元の配列における Zeta 変換を施せば良い. 詳しくは 以下のサイトを参考にすること.
計算量は である.