公式解説は上の桁から見ていますが、このユーザー解説では下の桁から見る方法をご紹介します。

解法

説明の都合上、入力の文字列の添字を \(1\) ずらし、\(s _ 0, \dots, s _ { N - 1 }\) と表しておきます。

\(0 \le i \le j \le N\) に対して、\(s _ i, \dots, s _ { j - 1}\) についてもとの問題を解いた答えを \(X _ { i, j }\) とおき、他の成分を全て \(0\) とおくことで行列 \(X\) を定義します。するともとの問題の答えは \(X _ { 0, N }\) です。

さて、suffix に帰着しましょう。長さ \(M - 1\) の suffix について同じ行列を \(X'\) と定義し、\(0 \le d \le 9\) に対し \(s _ i, \dots, s _ { j - 1 }\) の先頭の文字に、\(d\) と '?' 以外のものを含むような成分 \(X' _ { i, j }\) を \(0\) で上書きすることで \(X'\) から作られた行列を \(A _ d\) とおくと、

\[ X = A _ 9 A_ 8 \cdots A _ 0 \]

が成立します。

また長さ \(0\) の suffix については、文字列の個数が \(1\) 個以下なら \(1\)、さもなくば \(0\) です。

従って、サイズ \(N\) の正方行列同士の積が \(\mathcal D ( N )\) 時間で計算できるとき、この解法の計算時間は \(O \left \lparen \mathcal D ( N ) d M \right \rparen\) （ただし \(d\) は数字の種類数 \(10\)）です。

提出コード

変数 \(\mathtt{dp}\) が、ある suffix についての行列 \(X\) を表しており、全ての数字 '0'..='9' について行列積で遷移を行っています。

行列積をインラインに更新しているため、 全てのループを順向きにすると重複して数えてしまう（行列積を素直に for i: for j: for k: a[i][k] += a[i][j] * b[j][k] で計算するとまずいです…！）のでどこかしら逆順にする必要があるのですが、このコードでは数字の順序を逆順にすることで解決しています。

▼ Rust 31 ms

use proconio::{input, marker::Bytes};

fn main() {
    input! {
        h: usize,
        w: usize,
        s: [Bytes; h],
    }
    let mut dp = vec![vec![0_u64; h + 1]; h + 1];
    (0..h).for_each(|i| dp[i][i + 1] = 1);
    for p in (0..w).rev() {
        let mut swp = vec![vec![0; h + 1]; h + 1];
        (0..=h).for_each(|i| swp[i][i] = 1);
        for d in (b'0'..=b'9').rev() {
            for i in 0..h {
                for j in (i + 1..=h).take_while(|&j| s[j - 1][p] == d || s[j - 1][p] == b'?') {
                    for k in j..=h {
                        swp[i][k] += dp[i][j] * swp[j][k];
                        swp[i][k] %= 998_244_353;
                    }
                }
            }
        }
        dp = swp;
    }
    println!("{}", dp[0][h]);
}

ズル

今から書くことは正当性を証明していない（おそらく正当ではなく、たまたま通っているだけの）解法のため、ご了承いただけるとです。

上のコードではオーバーフローを防ぐために、掛け算をするたびに mod を取っていますが、行列積を計算するたびに mod を取るように変更しても AC することができました。

Rust 24 ms

\(p = 998244353\) とおき、\(N\) が最大である \(40\) とすると、行列積の要素の上界 \((p - 1) ^ 2 N \sim 2.16 \times 2 ^ { 64 }\) を得ますが、これが達成された場合には、オーバーフローをしてしまします。

ズルを利用して nalgebra で通す方法

今回は遷移が行列積で表せるため、AtCoder で使える nalgebra というクレートを使えます。ただサイズが \(41\) 以下と小さいこと、bruteforce なアルゴリズムでも上三角性により約 \(6\) 倍の高速化がなされることを考慮すると、あまり高速化は期待できないかもしれません。実際に試してみたところ、あまり速くはありませんでした。

Rust 33 ms

ズルで通らなかったときにもっとズルする方法

\(p = 998244353\) で割ったあまりを \(\lbrack 0, p \lbrack\) の範囲で表す代わりに \(\left \lbrack -( p - 1 ) / 2, ( p - 1 ) / 2 \right \rbrack\) の範囲で表すと、値の上界が \(1 / 4\) 程度になります。

しかしその代わり符号付き整数が必要になり、表せる整数の絶対値の最大値が \(1 / 2\) 程度になるため、これでもまだギリギリ正当性が証明できませんでした。実際この場合、上界 \((( p - 1 ) / 2 ) ^ 2 N \sim 1.08 \times 2 ^ { 63 }\) を得ますが、オーバーフローの可能性がわずかに残ってしまいます。

Rust 26 ms