\(N\) の桁数を \(n\) とします。

1. FPS への帰着

\(11\) の倍数の性質より、並べ替えた後の偶数桁目の数の和と、奇数番目の数の和は、\(11\) で割った余りが等しくなります。よって、全ての桁の数の和を \(s\) とすると、奇数桁目の合計を \(s/2 \bmod 11\) とする並べ替えの通り数（ただし先頭が \(0\) にならない）が答えるべきものになります。

さらに、先頭の \(0\) を許容した問題に答えることができれば、元のインスタンスと、\(0\) の個数を \(1\) つ減らしたインスタンスに対して答えを求めてその差分を見ることで、先頭の \(0\) を許容しない場合の問題に答えることができます。以下では、先頭の \(0\) を許容した問題を考えます。

\(i = 0,1,\dots,9\) に対し、\(N\) に含まれる \(i\) の個数を \(c_i\) とおきます。\(i\) のうち \(j_i\) 個を奇数桁目に置き、\(c_i-j_i\)個を偶数桁目に置くことにした時の並べ替えの総数は、\(\lfloor \frac{n}{2} \rfloor ! \lceil \frac{n}{2} \rceil!\prod_{i=0}^{9}\frac{1}{j_i!(c_i-j_i)!}\) と計算することができます。また、\(j_i\) の値の割り当てについては、

• 奇数桁目に並ぶ数字の個数の条件 \(\sum_{i=0}^{9} j_i=\lceil \frac{n}{2} \rceil\)
• 奇数桁目に並ぶ数字の和の条件 \(\sum_{i=0}^{9} ij_i\equiv s/2 \mod 11\)

という条件が課されます。よって、この条件を満たす \(j_0,\dots,j_9\) 全体にわたって \(\prod_{i=0}^{9}\frac{1}{j_i!(c_i-j_i)!}\) の合計を求めて、最後に \(\lfloor \frac{n}{2} \rfloor ! \lceil \frac{n}{2} \rceil!\) をかければ良いです。

ここで、FPS で考えるために、\(f_i(x,y) = \sum_{j=0}^{c_i} \frac{1}{j!(c_i-j)!} x^j y^{ij}\) とおきます。ただし \(\bmod (1-y^{11})\) で考えます（つまり \(y^{11}\) を \(y^0\) と同一視します）。すると、求めるべきものは、\(\prod_{i=0}^9 f_i(x,y)\) のうちの \(x^{\lceil \frac{n}{2} \rceil}y^{s/2\bmod 11}\) という項の係数になります。さらに、\(f_i(x,y)\) の表式を見ると、\(f_i(x,y)=\frac{1}{c_i!}(1+xy^i)^{c_i}\) と表せることが分かります。\(\frac{1}{c_i!}\) は後からかければいいので、結局 \(\prod_{i=0}^9 (1+xy^i)^{c_i}\) の特定の項が分かれば良いことになります。

ここまでが第一段階です。

2. 微分方程式への帰着

MOD が NTT-friendly であれば、\(g:=\prod_{i=0}^9 (1+xy^i)^{c_i}\) の特定の係数は、一度 FPS の \(\log\) を取った \(\sum_{i=0}^9 c_i\log(1+xy^i)\) を計算してから FPS の \(\exp\) を取れば求まるというような解法が考えられます。しかし、今回は MOD が NTT-friendly ではないため、このような解法は使えません。

そこで、微分方程式に帰着させることを考えます。\(g_i(x) = 1+xy^i\) とおくと、\(g_0g_1\dots g_9 \frac{\partial g}{\partial x} = (c_0 g'_0g_1\dots g_9 + c_1g_0g'_1\dots g_9+\dots + c_9g_0g_1 \dots g'_9) g\) です。\(g_0g_1\dots g_9\) と \(( c_0 g'_0g_1\dots g_9 + \dots + c_9 g_0 g_1 … g'_9)\) を前計算します（これらは \(x\) の高々 \(d\) 次式）。すると、一般に疎な FPS \(a(x),b(x)\) が与えられている時に、\(a(x)g(x)+b(x)g'(x)=0\) を満たす FPS \(g(x)\) は \(x\) の次数の小さい方から逐次的に計算することができます（こちらなどを参照）。今回の場合は、FPS の係数環が \(y\) についての多項式（ただし \(\bmod (1-y^{11})\)）となっていることに注意して、\(g\) の \(x^i\) の係数を \(i\) の昇順に計算していくことで、\(g\) の \(x^{\lceil \frac{n}{2} \rceil}\) の \(y^0\) から \(y^{10}\) までの係数が分かり、問題に答えることができます。

計算量については、\(g\) の \(x^i\) の係数を昇順に計算する部分がネックとなります。\(d\) を進数の底（今回は \(10\)）とすると、微分方程式の求解に \(O(nd)\) 回の FPS の係数の計算が必要です。また、FPS の係数は \(y\) についての多項式で、しかも積が現れるので、一回当たり \(O(d\log d)\) や \(O(d^2)\) という計算量がかかります。よって、合計で \(O(nd^2\log d)\) や \(O(nd^3)\) という計算量になります。

しかし、今回の問題は制約が厳しいため、この解法ではよほど高速化を工夫しない限り TLE となってしまうでしょう。

3. 多項式の補間

ここまでのボトルネックは、FPS の係数を求める際に、\(y\) の多項式の積を計算する部分です。この部分の高速化のアイデアとして、多項式自体の積を求めるのではなく、多点評価と補間で計算するアプローチを考えます。

つまり、\(y\) にいくつかの数を実際に代入して、FPS の係数を計算します。なお、今考えているのは \(1-y^{11}\) での剰余環なので、\(y\) に値を代入して多点評価をするには \(1\) の \(11\) 乗根を代入する必要があります。実は \(2^{31}-1\equiv 1 \mod 11\) であるため、\(\bmod\ 2^{31}-1\) 上では \(1\) の原始 \(11\) 乗根が存在します。実際、\(\bmod 2^{31}-1\) の原始根として \(7\) が取れて、\(7^{(2^{31}-2)/11}=7^{195225786}\) は原始 \(11\) 乗根の一つです。

よって、\(\omega\) を \(1\) の原始 \(11\) 乗根として、\(y\) に \(\omega^0,\omega^1,\dots,\omega^{10}\) を代入して、その結果から元の多項式を復元すれば良いです。これはまさしく有限体上の逆離散フーリエ変換（IDFT）です。

まとめると以下の通りです。

• \(y\) に \(\omega^0,\omega^1,\dots,\omega^{10}\) を代入して、以下の問題を解く。
  • \(g\) が満たす \(1\) 変数微分方程式 \(g_0g_1\dots g_9 \frac{\partial g}{\partial x} = (c_0 g'_0g_1\dots g_9 + c_1g_0g'_1\dots g_9+\dots + c_9g_0g_1 \dots g'_9) g\) を解き、\(g\) の \(x^{\lceil \frac{n}{2} \rceil}\) の係数を求める
• 求めた係数から、\(g\) の \(x^{\lceil \frac{n}{2} \rceil}\) の係数を \(y\) についての多項式として見た時に何になるかを復元する（IDFT）。
• 求めた多項式の \(y^{s/2\bmod 11}\) の係数に、\(\lfloor \frac{n}{2} \rfloor ! \lceil \frac{n}{2} \rceil!\) や \(\frac{1}{c_i!}\) をかけて、先頭の \(0\) を許容した問題の答えとする。
• \(N\) に \(0\) が含まれる場合は、\(0\) の個数を \(1\) つ減らした上で同様に問題を解いて、その差分を最終的な答えとして出力する。

\(d\) 種類の \(y\) の値について、それぞれ \(O(nd)\) 時間で微分方程式を解くため、全体で \(O(nd^2)\) 時間となります。IDFTの部分には \(n\) がかからないため、計算量のネックにはなりません。以上により AC を取ることができます。なお、MOD が \(2^{31}-1\) であることに注目して、剰余をビット演算で求めることにすると、より高速に動作するでしょう。