Submission #39443062

---

Source Code Expand

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <ciso646>
#include <cmath>
#include <complex>
#include <cstdio>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < n; i++)
#define per(i, n) for (int i = n - 1; i >= 0; i--)
#define Rep(i, sta, n) for (int i = sta; i < n; i++)
#define Per(i, sta, n) for (int i = n - 1; i >= sta; i--)
#define fi first
#define se second
typedef long double ld;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
int dx[8] = {1, -1, 0, 0, 1, 1, -1, -1};
int dy[8] = {0, 0, 1, -1, 1, -1, 1, -1};
template <class T> using max_heap = priority_queue<T>;
template <class T> using min_heap = priority_queue<T, vector<T>, greater<>>;
template <class T> bool chmax(T &a, const T &b) {
   if (a < b) {
      a = b;
      return 1;
   }
   return 0;
}
template <class T> bool chmin(T &a, const T &b) {
   if (b < a) {
      a = b;
      return 1;
   }
   return 0;
}

template <int mod> struct ModInt {
   long long x;
   static constexpr int MOD = mod;

   ModInt() : x(0) {}
   ModInt(long long y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

   explicit operator int() const { return x; }

   ModInt &operator+=(const ModInt &p) {
      if ((x += p.x) >= mod) x -= mod;
      return *this;
   }
   ModInt &operator-=(const ModInt &p) {
      if ((x += mod - p.x) >= mod) x -= mod;
      return *this;
   }
   ModInt &operator*=(const ModInt &p) {
      x = (int)(1LL * x * p.x % mod);
      return *this;
   }
   ModInt &operator/=(const ModInt &p) {
      *this *= p.inverse();
      return *this;
   }

   ModInt operator-() const { return ModInt(-x); }
   ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
   ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
   ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
   ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
   ModInt operator%(const ModInt &p) const { return ModInt(0); }

   bool operator==(const ModInt &p) const { return x == p.x; }
   bool operator!=(const ModInt &p) const { return x != p.x; }

   ModInt inverse() const {
      int a = x, b = mod, u = 1, v = 0, t;
      while (b > 0) {
         t = a / b;
         a -= t * b;
         swap(a, b);
         u -= t * v;
         swap(u, v);
      }
      return ModInt(u);
   }

   ModInt power(long long n) const {
      ModInt ret(1), mul(x);
      while (n > 0) {
         if (n & 1) ret *= mul;
         mul *= mul;
         n >>= 1;
      }
      return ret;
   }

   ModInt power(const ModInt p) const { return ((ModInt)x).power(p.x); }

   friend ostream &operator<<(ostream &os, const ModInt<mod> &p) { return os << p.x; }
   friend istream &operator>>(istream &is, ModInt<mod> &a) {
      long long x;
      is >> x;
      a = ModInt<mod>(x);
      return (is);
   }
};

using modint = ModInt<mod>;

modint dp[45][45][45][10];
bool visited[45][45][45][10];

int N, M;
int S[45][45];

bool check(int L, int R, int K, int mi) {
   Rep(i, L, R) {
      if (S[i][K] != -1 && S[i][K] != mi) return false;
   }
   return true;
}

modint calc_dp(int L, int R, int K, int mi) {
   if (visited[L][R][K][mi]) return dp[L][R][K][mi];
   if (R - L == 1) {
      if (S[L][K] != -1 && S[L][K] != mi) {
         visited[L][R][K][mi] = true;
         return 0;
      } else {
         modint res = 1;
         Rep(j, K + 1, M) if (S[L][j] == -1) res *= 10;
         visited[L][R][K][mi] = true;
         dp[L][R][K][mi] = res;
         return res;
      }
   }
   modint res = 0;
   if (!check(L, R, K, mi)) {
      visited[L][R][K][mi] = true;
      return 0;
   }
   Rep(x, L + 1, R) {
      if (!check(L, x, K, mi)) continue;
      if (K == M - 1)
         if (x > L + 1) continue;
      modint S1 = 0, S2 = 0;
      rep(j, 10) { S1 += calc_dp(L, x, K + 1, j); }
      Rep(j, mi + 1, 10) { S2 += calc_dp(x + 1, R, K, j); }
      res += S1 * S2;
   }
   visited[L][R][K][mi] = true;
   dp[L][R][K][mi] = res;
   return res;
}

void solve() {
   cin >> N >> M;
   rep(i, N) {
      string s;
      cin >> s;
      rep(j, M) {
         if (s[j] == '?') {
            S[i][j] = -1;
         } else {
            S[i][j] = s[j] - '0';
         }
      }
   }
   modint ans = 0;
   rep(i, 10) ans += calc_dp(0, N, 0, i);
   cout << ans << endl;
}

int main() {
   ios::sync_with_stdio(false);
   cin.tie(0);
   cout << fixed << setprecision(50);
   solve();
}

Submission Info

Judge Result