fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define FOR(i, a, b) for (int i = a; i <= b; ++i)
  4. #define FORD(i, a, b) for (int i = a; i >= b; --i)
  5. #define ll long long
  6.  
  7. using namespace std;
  8.  
  9. const int N = 1e6 + 5;
  10. const ll mod = 1e9 + 19972207;
  11. int l, u, v;
  12. ll f[N][2], g[N][2];
  13. string a, b;
  14.  
  15. void nhap() {
  16.     cin >> l >> a >> b;
  17. }
  18.  
  19. void add(ll &a, const ll &b) {
  20.     a += b;
  21.     if (a >= mod) a -= mod;
  22. }
  23.  
  24. ll pw(ll a, ll b) {
  25.     ll res = 1;
  26.     while (b) {
  27.         if (b & 1) res = res * a % mod;
  28.         a = a * a % mod;
  29.         b >>= 1;
  30.     }
  31.     return res;
  32. }
  33.  
  34. void giai() {
  35.     int u = a.size(), v = b.size();
  36.     a = " " + a;
  37.     b = " " + b;
  38.  
  39.     f[0][0] = g[0][0] = 1;
  40.     FOR(i, 1, min(u, l)) FOR(j, 0, 1) if (f[i - 1][j])
  41.     FOR(k, 0, (j ? 25 : a[i] - 'a')) add(f[i][j | (k < (a[i] - 'a'))], f[i - 1][j]);
  42.  
  43.     FOR(i, 1, min(v, l)) FOR(j, 0, 1) if (g[i - 1][j])
  44.     FOR(k, 0, (j ? 25 : b[i] - 'a')) add(g[i][j | (k < (b[i] - 'a'))], g[i - 1][j]);
  45.  
  46.     ll L, R;
  47.     if (v < l) R = g[v][1] * pw(26, l - v) % mod;
  48.     else if (v == l) R = g[l][1];
  49.     else if (v > l) R = (g[l][0] + g[l][1]) % mod;
  50.  
  51.     if (u < l) L = f[u][1] * pw(26, l - u) % mod;
  52.     else if (u >= l) L = (f[l][0] + f[l][1]) % mod;
  53.  
  54.     cout << (R - L + mod) % mod;
  55. }
  56.  
  57. int main() {
  58.     ios_base::sync_with_stdio(0);
  59.     cin.tie(0); cout.tie(0);
  60.  
  61.     #define name "strings"
  62.  
  63.     if (fopen(name".inp", "r")) {
  64.         freopen(name".inp", "r", stdin);
  65.         freopen(name".out", "w", stdout);
  66.     }
  67.  
  68.     nhap();
  69.     giai();
  70.  
  71.     return 0;
  72. }
  73.  
Success #stdin #stdout 0.01s 5608KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1019972206
https://ideone.com/KunxPy
language:
C++14 (clang 8.0)
created:
5 hours 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!