Bundle
Copy
#line 1 "test/aoj_3110.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3110"
#include <cstdio>
#include <array>
#include <string>
#line 1 "ModularArithmetic/modint.cpp"
/**
* @brief 合同算術用クラス
* @author えびちゃん
*/
#include <cstdint>
#include <limits>
#include <type_traits>
#include <utility>
template <intmax_t Modulo>
class modint {
public:
using value_type = typename std::conditional<
(0 < Modulo && Modulo < std::numeric_limits<int>::max() / 2), int, intmax_t
>::type;
private:
static constexpr value_type S_cmod = Modulo; // compile-time
static value_type S_rmod; // runtime
value_type M_value = 0;
static constexpr value_type S_inv(value_type n, value_type m) {
value_type x = 0;
value_type y = 1;
value_type a = n;
value_type b = m;
for (value_type u = y, v = x; a;) {
value_type q = b / a;
std::swap(x -= q*u, u);
std::swap(y -= q*v, v);
std::swap(b -= q*a, a);
}
if ((x %= m) < 0) x += m;
return x;
}
static value_type S_normalize(intmax_t n, value_type m) {
if (n >= m) {
n %= m;
} else if (n < 0) {
if ((n %= m) < 0) n += m;
}
return n;
}
public:
modint() = default;
modint(intmax_t n): M_value(S_normalize(n, get_modulo())) {}
modint& operator =(intmax_t n) {
M_value = S_normalize(n, get_modulo());
return *this;
}
modint& operator +=(modint const& that) {
if ((M_value += that.M_value) >= get_modulo()) M_value -= get_modulo();
return *this;
}
modint& operator -=(modint const& that) {
if ((M_value -= that.M_value) < 0) M_value += get_modulo();
return *this;
}
modint& operator *=(modint const& that) {
intmax_t tmp = M_value;
tmp *= that.M_value;
M_value = tmp % get_modulo();
return *this;
}
modint& operator /=(modint const& that) {
intmax_t tmp = M_value;
tmp *= S_inv(that.M_value, get_modulo());
M_value = tmp % get_modulo();
return *this;
}
modint& operator ++() {
if (++M_value == get_modulo()) M_value = 0;
return *this;
}
modint& operator --() {
if (M_value-- == 0) M_value = get_modulo()-1;
return *this;
}
modint operator ++(int) { modint tmp(*this); ++*this; return tmp; }
modint operator --(int) { modint tmp(*this); --*this; return tmp; }
friend modint operator +(modint lhs, modint const& rhs) { return lhs += rhs; }
friend modint operator -(modint lhs, modint const& rhs) { return lhs -= rhs; }
friend modint operator *(modint lhs, modint const& rhs) { return lhs *= rhs; }
friend modint operator /(modint lhs, modint const& rhs) { return lhs /= rhs; }
modint operator +() const { return *this; }
modint operator -() const {
if (M_value == 0) return *this;
return modint(get_modulo() - M_value);
}
friend bool operator ==(modint const& lhs, modint const& rhs) {
return lhs.M_value == rhs.M_value;
}
friend bool operator !=(modint const& lhs, modint const& rhs) {
return !(lhs == rhs);
}
value_type get() const { return M_value; }
static value_type get_modulo() { return ((S_cmod > 0)? S_cmod: S_rmod); }
template <int M = Modulo, typename Tp = typename std::enable_if<(M <= 0)>::type>
static Tp set_modulo(value_type m) { S_rmod = m; }
};
template <intmax_t N>
constexpr typename modint<N>::value_type modint<N>::S_cmod;
template <intmax_t N>
typename modint<N>::value_type modint<N>::S_rmod;
#line 1 "utility/literals.cpp"
/**
* @brief ユーザ定義リテラル
* @author えびちゃん
*/
#include <cstddef>
#line 11 "utility/literals.cpp"
constexpr intmax_t operator ""_jd(unsigned long long n) { return n; }
constexpr uintmax_t operator ""_ju(unsigned long long n) { return n; }
constexpr size_t operator ""_zu(unsigned long long n) { return n; }
constexpr ptrdiff_t operator ""_td(unsigned long long n) { return n; }
constexpr int8_t operator ""_i8(unsigned long long n) { return n; }
constexpr int16_t operator ""_i16(unsigned long long n) { return n; }
constexpr int32_t operator ""_i32(unsigned long long n) { return n; }
constexpr int64_t operator ""_i64(unsigned long long n) { return n; }
constexpr uint8_t operator ""_u8(unsigned long long n) { return n; }
constexpr uint16_t operator ""_u16(unsigned long long n) { return n; }
constexpr uint32_t operator ""_u32(unsigned long long n) { return n; }
constexpr uint64_t operator ""_u64(unsigned long long n) { return n; }
#line 1 "utility/make/vector.cpp"
/**
* @brief 多次元 vector の作成
* @author えびちゃん
*/
#line 10 "utility/make/vector.cpp"
#include <type_traits>
#include <vector>
namespace detail {
template <typename Tp, size_t Nb>
auto make_vector(std::vector<size_t>& sizes, Tp const& x) {
if constexpr (Nb == 1) {
return std::vector(sizes[0], x);
} else {
size_t size = sizes[Nb-1];
sizes.pop_back();
return std::vector(size, make_vector<Tp, Nb-1>(sizes, x));
}
}
} // detail::
template <typename Tp, size_t Nb>
auto make_vector(size_t const(&sizes)[Nb], Tp const& x = Tp()) {
std::vector<size_t> s(Nb);
for (size_t i = 0; i < Nb; ++i) s[i] = sizes[Nb-i-1];
return detail::make_vector<Tp, Nb>(s, x);
}
#line 10 "test/aoj_3110.test.cpp"
constexpr intmax_t mod = 1000'000'007;
using mi = modint<mod>;
int main() {
char buf[262144];
scanf("%s", buf);
std::string s = buf;
scanf("%s", buf);
std::string t = buf;
size_t n = s.length();
auto dp0 = make_vector({n+1, 2_zu}, mi(0));
auto dp1 = make_vector({n+1, 2_zu}, mi(0));
size_t const loose = 0;
size_t const tight = 1;
std::array<size_t, 2> const tightness{{loose, tight}};
dp0[0][tight] = 1;
for (size_t i = 0; i < n; ++i) {
for (size_t j: tightness) {
for (int k = 0; k <= 9; ++k) {
if (t[i] != '?' && t[i] != '0'+k) continue;
if (j == tight && '0'+k > s[i]) break;
size_t nj = ((j == tight && '0'+k == s[i])? tight: loose);
dp0[i+1][nj] += dp0[i][j];
dp1[i+1][nj] += dp1[i][j] * 10 + dp0[i][j] * k;
}
}
}
printf("%d\n", (dp1[n][loose] + dp1[n][tight]).get());
}