fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define rep(i, n) for(int i = 1; (i) <= (n); ++i)
  6. #define forn(i, l, r) for(int i = (l); i <= (r); ++i)
  7. #define ford(i, r, l) for(int i = (r); i >= (l); --i)
  8. #define FOR(i, n) for(int i = 0; i < (n); ++i)
  9. #define FORD(i, n) for(int i = ((n) - 1); i >= 0; --i)
  10. #define fi first
  11. #define se second
  12. #define pii pair<int, int>
  13. #define pll pair<ll, ll>
  14. #define pb push_back
  15. #define task "brentford40mu"
  16. #define sz(a) int(a.size())
  17. #define C(x, y) make_pair(x, y)
  18. #define all(a) (a).begin(), (a).end()
  19. #define bit(i, mask) (mask >> i & 1)
  20.  
  21. template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
  22. template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
  23.  
  24. inline int readInt()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
  25. inline ll readLong()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll  n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
  26. inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}
  27.  
  28.  
  29. const int N = 1e6 + 3;
  30. const int K = 11;
  31. const int MOD = 1e9 + 19972207;
  32. const int G = 2521;
  33.  
  34.  
  35.  
  36. int n;
  37.  
  38. string s, t;
  39.  
  40. struct modular {
  41.   int value;
  42.  
  43.   modular(int v = 0) {value = v; if(value < 0) value += MOD;}
  44.  
  45.   modular& operator += (modular const& b) {value += b.value; if (value >= MOD) value -= MOD; return *this;}
  46.   modular& operator -= (modular const& b) {value -= b.value; if (value < 0) value += MOD; return *this;}
  47.   modular& operator *= (modular const& b) {value = 1ll * value * b.value % MOD; return *this;}
  48.  
  49.   friend modular bin_pow(modular a, int y) {
  50.     modular res = 1; while (y) { if (y & 1) res *= a; a *= a; y >>= 1; }
  51.     return res;
  52.   }
  53.   friend modular inverse(modular a) { return bin_pow(a, MOD - 2); }
  54.  
  55.   modular& operator/=(modular const& b) { return *this *= inverse(b); }
  56.   friend modular operator+(modular a, modular const b) { return a += b; }
  57.   friend modular operator-(modular a, modular const b) { return a -= b; }
  58.   friend modular operator-(modular const a) { return 0 - a; }
  59.   friend modular operator*(modular a, modular const b) { return a *= b; }
  60.   friend modular operator/(modular a, modular const b) { return a /= b; }
  61.   friend ostream& operator<<(std::ostream& os, modular const& a) {return os << a.value;}
  62.   friend bool operator==(modular const& a, modular const& b) {return a.value == b.value;}
  63.   friend bool operator!=(modular const& a, modular const& b) {return a.value != b.value;}
  64. };
  65.  
  66.  
  67. struct node
  68. {
  69.     modular sum_x, sum_y, prod, cnt;
  70. };
  71.  
  72. node dp[N][4];
  73.  
  74. int f = 0;
  75. int get(int x, int y)
  76. {
  77.     return (x == y) ? 0 : (x < y ? 1 : 2);
  78. }
  79.  
  80. int get_sum(int l, int  r)
  81. {
  82.     return r * (r + 1) / 2 - l * (l - 1) / 2;
  83. }
  84.  
  85. array<int, 4> c[11][11][3];
  86.  
  87.  
  88. void solve()
  89. {
  90.     cin >> s >> t;
  91.     n = sz(s);
  92.  
  93.     forn(i, 0, 9)
  94.         forn(j, 0, 9)
  95.         {
  96.             int x = get(i, j);
  97.             forn(u, 0, 1)
  98.                 forn(v, 0, 1)
  99.                 {
  100.                     int a = u ? 10 : i, b = v ? 10 : j;
  101.                     c[a][b][x][0] += i;
  102.                     c[a][b][x][1] += j;
  103.                     c[a][b][x][2] += i * j;
  104.                     c[a][b][x][3] += 1;
  105.                 }
  106.         }
  107.  
  108.  
  109.     forn(i, 0, n)
  110.     {
  111.         forn(x, 0, 3)
  112.         {
  113.             if(i == 0)
  114.             {
  115.                 dp[i][x] = {0, 0, 0, x == 3};
  116.                 continue;
  117.             }
  118.  
  119.             node &res = dp[i][x];
  120.  
  121.             res = {0, 0, 0, 0};
  122.  
  123.             function<void(array<int, 4>, node)> modify = [&](array<int, 4> a, node cur) {
  124.                 res.sum_x += cur.sum_x * 10 * a[3] + cur.cnt * a[0];
  125.                 res.sum_y += cur.sum_y * 10 * a[3] + cur.cnt * a[1];
  126.                 res.prod += a[3] * 100 * cur.prod + 10 * (cur.sum_x * a[1] + cur.sum_y * a[0])
  127.                         + cur.cnt * a[2];
  128.                 res.cnt += cur.cnt * a[3];
  129.  
  130.             };
  131.  
  132.             int u = s[i - 1] == '?' ? 10 : s[i - 1] - '0';
  133.             int v = t[i - 1] == '?' ? 10 : t[i - 1] - '0';
  134.  
  135.             forn(z, 0, 2)
  136.                 modify(c[u][v][z], dp[i - 1][x | z]);
  137.         }
  138.     }
  139.     cout << dp[n][0].prod;
  140. }
  141.  
  142. signed main()
  143. {
  144.     ios_base::sync_with_stdio(0);
  145.     cin.tie(0); cout.tie(0);
  146.     int TC = 1;
  147.  
  148.     if(fopen(task".inp", "r"))
  149.     {
  150.         freopen(task".inp", "r", stdin);
  151.         freopen(task".out", "w", stdout);
  152.     }
  153.  
  154.     int sub = 1;
  155.  
  156.  
  157.     while(TC--)
  158.     {
  159.         solve();
  160.     }
  161.  
  162.     return 0;
  163. }
  164.  
Success #stdin #stdout 0.02s 66212KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/xtzvho
language:
C++14 (clang 8.0)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!