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

\(b\) 桁の整数 \(m\) の答えへの貢献度を考えます。つまり、 \(T\) として末尾に追加する文字列を \(m\) 以外で全て同じ長さの 0 からなる文字列に置き換えた際の答えを求めることを考えます。

まず、\(P\) の中で \(m\) より後ろにある整数のうち \(k\) 桁のものが \(i_k\) 個あるとすると、 \(f(P)\) への \(m\) の貢献度は \(m10^{\sum_k ki_k}\) となります。したがって、 \(C_k\) を \(1\) 以上 \(N\) 以下で \(m\) でない整数のうち \(k\) 桁の整数の個数とすると、

• \(k=1,2,\ldots,B\) に対し \(C_k\) 個の中から \(m\) より後ろに並ぶ \(i_k\) 個の \(k\) 桁の整数を選ぶ方法が \(\displaystyle \binom{C_k}{i_k}\) 通り
• \(m\) より後ろにある \(\displaystyle \sum_k i_k\) 個の整数を並び替える方法が \(\displaystyle \left(\sum_k i_k\right)!\) 通り
• \(m\) より前にある \(\displaystyle N-1-\sum_k i_k\) 個の整数を並び替える方法が \(\displaystyle \left(N-1-\sum_ki_k\right)!\) 通り

であることから、 \(m\) の答えへの貢献度は

\[\sum_{0\le i_k\le C_k\ (1\le k\le B)} m10^{\sum_k ki_k}\left(\prod_k \binom{C_k}{i_k}\right)\left(\sum_k i_k\right)!\left(N-1-\sum_ki_k\right)!\]

であることが分かります。ここで、 \(\displaystyle \sum_{0\le i_k\le C_k\ (1\le k\le B)}\) は \(k=1,2,\ldots,B\) に対し \(0\le i_k\le C_k\) を満たす長さ \(B\) の整数列 \(i\) 全てに対するシグマの中の関数の総和を表しています。

さらに、 \(\displaystyle F_k(x)=\sum_{i=0}^{C_k}\binom{C_k}{i}10^{ki}x^i=(1+10^k x)^{C_k}\) とすると、 \(m\) の答えへの貢献度は \(\displaystyle \sum_i f_ix^i=\prod_kF_k(x)\) に対し \(\displaystyle m\sum_{i=0}^{N-1}f_i i!(N-1-i)!\) と書くことができます。また、 \(1\) 以上 \(N\) 以下の整数のうち \(k\) 桁であるものの個数を \(C_k^0\) と書き、 \(\displaystyle F_k^0(x)=\sum_{i=0}^{C_k^0}\binom{C_k^0}{i}10^{ki}x^i=(1+10^k x)^{C_k^0}\) とすると、 \(\displaystyle F^0(x)=\prod_k F_k^0(x)\) に対し \(\displaystyle \sum_i f_ix^i=\frac{F^0(x)}{1+10^b x}\) となります。

\(F^0\) の計算には \(B-1\) 回の畳み込みの計算が必要ですが、 \(F_k\) の次数が \(C_k^0=O(10^k)\) なので次数の小さい \(2\) つの多項式から順に畳み込みの計算をすることでこの計算は \(\displaystyle O\left(\sum_{k=2}^B 10^k\log10^k\right)=O(B10^B)\) 時間で可能です。

さらに、 \(F^0\) の値は \(b\) に依存しません。したがって、最初に \(F^0\) を計算し、そこから各 \(m\) の桁数 \(b\) に対し \(\displaystyle \frac{F^0(x)}{1+10^b x}\) を計算すれば良いです。この多項式の除算は筆算と同じ要領で計算することで各 \(b\) に対し \(O(N)\) 時間で計算することが可能です。

\(m\) の桁数は \(B\) 以下で \(B=O(\log N)\) なので、以上を適切に実装することで \(O(N\log N)\) 時間でこの問題を解くことができます。

実装例(C++)

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using mint = atcoder::modint998244353;
int main()
{
    int n;
    cin >> n;
    int B = to_string(n).size();
    vector<mint> fact(n + 1), finv(n + 1);
    fact[0] = 1;
    for (int i = 1; i <= n; i++)
        fact[i] = i * fact[i - 1];
    finv[n] = fact[n].inv();
    for (int i = n; i > 0; i--)
        finv[i - 1] = i * finv[i];
    auto comb = [&](int n, int k) -> mint
    { return fact[n] * finv[k] * finv[n - k]; };
    vector<int> ten(B + 1);
    ten[0] = 1;
    for (int i = 1; i <= B; i++)
        ten[i] = 10 * ten[i - 1];
    vector<int> c(B + 1);
    for (int i = 1; i <= n; i++)
        c[to_string(i).size()]++;
    vector<mint> F0 = {1};
    for (int k = 1; k <= B; k++)
    {
        vector<mint> new_f(c[k] + 1);
        mint ten_c = 1;
        for (int i = 0; i < c[k] + 1; i++)
        {
            new_f[i] = comb(c[k], i) * ten_c;
            ten_c *= ten[k];
        }
        F0 = atcoder::convolution(F0, new_f);
    }
    F0.push_back(0);
    mint ans = 0;
    for (int b = 1; b <= B; b++)
    {
        auto f = F0;
        for (int i = 0; i < n; i++)
            f[i + 1] -= ten[b] * f[i];
        mint res = 0;
        for (int i = 0; i < n; i++)
            res += f[i] * fact[i] * fact[n - 1 - i];
        long long le = ten[b - 1], ri = min(ten[b], n + 1);
        ans += res * (ri * (ri - 1) / 2 - le * (le - 1) / 2);
    }
    cout << ans.val() << endl;
}