fork(2) download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <math.h>
  4. #include <algorithm>
  5. #define inf 1000000000
  6. #define MOD 1000000007
  7.  
  8. using namespace std;
  9. typedef long long ll;
  10.  
  11. string s, s2;
  12. ll cnt[26];
  13. ll fact[1001000];
  14. ll _fact[1001000];
  15.  
  16. ll bin_pow(ll x, ll n)
  17. {
  18. 	if (!n)
  19. 		return 1;
  20. 	if (n % 2)
  21. 		return (x*bin_pow(x, n - 1)) % MOD;
  22. 	ll y = bin_pow(x, n / 2);
  23. 	return (y*y) % MOD;
  24. }
  25.  
  26. void init()
  27. {
  28. 	fact[0] = 1;
  29. 	for (int i = 1; i < 1001000; i++)
  30. 		fact[i] = (fact[i - 1] * i) % MOD;
  31. 	_fact[1000999] = bin_pow(fact[1000999], MOD - 2);
  32. 	for (int i = 1000998; i >= 0; i--)
  33. 		_fact[i] = (_fact[i + 1] * (i + 1)) % MOD;
  34. }
  35.  
  36. ll f(string str)
  37. {
  38. 	ll res = 0;
  39. 	ll perm = fact[s.size()];
  40. 	for (int i = 0; i < 26; i++)
  41. 		cnt[i] = 0;
  42. 	for (int i = 0; i < s.size(); i++)
  43. 		cnt[s[i] - 'a']++;
  44. 	for (int i = 0; i < 26; i++)
  45. 		perm = (perm * _fact[cnt[i]]) % MOD;
  46. 	for (int i = 0; i < s.size(); i++)
  47. 	{
  48. 		perm = (perm * _fact[s.size() - i]) % MOD;
  49. 		perm = (perm * fact[s.size() - i - 1]) % MOD;
  50. 		for (int j = 0; j < str[i] - 'a'; j++)
  51. 		{
  52. 			if (!cnt[j])
  53. 				continue;
  54. 			perm = (perm * fact[cnt[j]]) % MOD;
  55. 			cnt[j]--;
  56. 			perm = (perm * _fact[cnt[j]]) % MOD;
  57. 			ll add = fact[s.size() - i - 1];
  58. 			res = (res + perm) % MOD;
  59. 			perm = (perm * fact[cnt[j]]) % MOD;
  60. 			cnt[j]++;
  61. 			perm = (perm * _fact[cnt[j]]) % MOD;
  62. 		}
  63. 		if (!cnt[str[i] - 'a'])
  64. 			break;
  65. 		perm = (perm * fact[cnt[str[i] - 'a']]) % MOD;
  66. 		cnt[str[i] - 'a']--;
  67. 		perm = (perm * _fact[cnt[str[i] - 'a']]) % MOD;
  68. 	}
  69. 	return res;
  70. }
  71.  
  72. int main()
  73. {
  74. 	init();
  75. 	cin >> s >> s2;
  76. 	cout << (f(s2) - f(s) - 1 + MOD) % MOD << endl;
  77. }
Success #stdin #stdout 0.01s 30880KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000006
https://ideone.com/fjz8E0
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!