fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int main() {
  6.   ios::sync_with_stdio(false);
  7.   cin.tie(nullptr);
  8.   int n, k;
  9.   string s, t;
  10.   cin >> n >> k >> s >> t;
  11.   const int md = 1e9 + 7;
  12.   auto mul = [&](int a, int b) -> int {
  13.     return (long long) a * b % md;
  14.   };
  15.   auto add = [&](int a, int b) {
  16.     return (a += b - md) < 0 ? a + md : a;
  17.   };
  18.   auto inv = [&](int a) {
  19.     int s = 1, t = 0, b = md;
  20.     while (b) {
  21.       int q = a / b;
  22.       swap(s -= q * t, t);
  23.       swap(a -= q * b, b);
  24.     }
  25.     return s < 0 ? s + md : s;
  26.   };
  27.   vector<int> pw(k + 1);
  28.   pw[0] = 1;
  29.   for (int i = 0; i < k; i++) {
  30.     pw[i + 1] = mul(pw[i], 25);
  31.   }
  32.   vector<int> fact(n + 1), ifact(n + 1);
  33.   fact[0] = 1;
  34.   for (int i = 0; i < n; i++) {
  35.     fact[i + 1] = mul(i + 1, fact[i]);
  36.   }
  37.   ifact[n] = inv(fact[n]);
  38.   for (int i = n - 1; i >= 0; i--) {
  39.     ifact[i] = mul(i + 1, ifact[i + 1]);
  40.   }
  41.   auto binom = [&](int n, int m) {
  42.     if (n < m) {
  43.       return 0;
  44.     }
  45.     return mul(fact[n], mul(ifact[n - m], ifact[m]));
  46.   };
  47.   int ans = 0;
  48.   for (int i = 0; i < n; i++) {
  49.     if (k == 0) {
  50.       break;
  51.     }
  52.     int d;
  53.     int ti = t[i] - 'a';
  54.     int si = s[i] - 'a';
  55.     if (ti <= si) {
  56.       d = mul(ti, mul(pw[k - 1], binom(n - i - 1, k - 1)));
  57.     } else {
  58.       d = mul(pw[k], binom(n - i - 1, k));
  59.       if (ti > 1) {
  60.         d = add(d, mul(ti - 1, mul(binom(n - i - 1, k - 1), pw[k - 1])));
  61.       }
  62.     }
  63.     ans = add(ans, d);
  64.     k -= (si != ti);
  65.   }
  66.   cout << add(ans, 1) << endl;
  67.   cerr << "Time: " << double(clock()) / CLOCKS_PER_SEC << '\n';
  68.   return 0;
  69. }
  70.  
Success #stdin #stdout #stderr 0s 4480KB
comments (?)
stdin
copy 
4 1
abcd
bbcd
stdout
copy 
76
stderr
copy 
Time: 0.003255
https://ideone.com/Qx6Zp3
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!