fork download
copy 
  1. #include <cmath>
  2. #include <ctime>
  3. #include <iostream>
  4. #include <string>
  5. #include <vector>
  6. #include<cstdio>
  7. #include<sstream>
  8. #include<algorithm>
  9. #include<cstdlib>
  10. #include<cstring>
  11. #include<map>
  12. #include<set>
  13. #include<queue>
  14. #include<cctype>
  15. #include <iomanip>
  16. #include <string>
  17. #include <sstream>
  18. #include <functional>
  19. #include <numeric>
  20. #include <stack>
  21. #include <climits>
  22. #include <float.h>
  23. #include<unordered_map>
  24. #include <bitset>
  25. #include <tuple>
  26.  
  27. using namespace std;
  28. #define pb push_back
  29. #define mp make_pair
  30. #define ff first
  31. #define ss second
  32. #define rep(i, n) for(int i = 0; i < (n); ++i)
  33. #define f(i,a,b) for(int i=a;i<b;i++)
  34. #define F(i,a,b) for(int i=a;i>=    b;i--)
  35. #define sz(a) ((int)a.size())
  36. #define all(c) c.begin(), c.end()
  37. #define fast ios_base::sync_with_stdio(0);cin.tie(0);
  38. #define dbgs(x) cerr << (#x) << " --> " << (x) << ' '
  39. #define dbg(x) cerr << (#x) << " --> " << (x) << endl
  40. #define sz(a) ((int)a.size())
  41. #define endl '\n' 
  42.  
  43. //#define fast ios_base::sync_with_stdio(0);cin.tie(0) ; 
  44. typedef long long ll;
  45. typedef unsigned long long ull;
  46. typedef pair <ll, ll> pll;
  47. typedef vector<ll> vll;
  48. typedef vector<int> vi;
  49. typedef vector<pair<int, int> > vpii;
  50. typedef map<int, int> mii;
  51. typedef map<ll, ll> mll;
  52. typedef pair<int, int> pii;
  53. typedef pair<string, int> psi;
  54. typedef long double ld;
  55.  
  56. int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); }
  57.  
  58. ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }
  59.  
  60. ll poww(ll a, ll b) {
  61. 	if (b == 0) return 1;
  62. 	ll tmp = poww(a, b / 2);
  63. 	return (b & 1 ? a * tmp * tmp : tmp * tmp);
  64. }
  65.  
  66. string itos(ll i) { string s = ""; 	while (i) { s += char(i % 10 + '0'); i /= 10; } reverse(all(s));  return s; }
  67.  
  68. ll stoi(string &s) { ll tot = 0; for (int i = (int)s.length() - 1, j = 1; i >= 0; i--, j *= 10) { tot += j * (s[i] + '0'); }  return tot; }
  69.  
  70. int months[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
  71.  
  72. using namespace std;
  73.  
  74.  
  75. void tt() {
  76. #ifndef online	_judge
  77. 	freopen("test.txt", "r", stdin);
  78. 	//freopen("output.txt", "w", stdout);
  79. #endif
  80. }
  81.  
  82.  
  83.  
  84. int mod = 1e9 + 7;
  85.  
  86. const int MAX = 1e5 + 10;
  87. ll fact[MAX], ifact[MAX];
  88.  
  89. int pre[26][MAX];
  90.  
  91. int n;
  92.  
  93. map<int, int> mpp;
  94. set<int> od, ev;
  95.  
  96.  
  97.  
  98.  
  99. ll pwmod(ll num, ll pow) {
  100.  
  101. 	if (pow == 0) { return 1; }
  102.  
  103. 	ll x = 1ll * pwmod(num, pow / 2) % mod; ;
  104.  
  105. 	ll res = 1ll * x % mod * x % mod;
  106.  
  107. 	if (pow & 1) res = res * num % mod;
  108.  
  109. 	return res;
  110.  
  111. }
  112.  
  113. int inv(int num) {
  114.  
  115.  
  116. 	return pwmod(num, mod - 2) % mod; ;
  117. }
  118.  
  119. int main() {
  120.  
  121. 	///tt(); 
  122.  
  123. 	mod = 1e9 + 7;
  124. 	string s;
  125. 	cin >> s;
  126.  
  127.  
  128. 	n = (int)s.length();
  129.  
  130. 	s = "#" + s;
  131.  
  132.  
  133. 	for (int i = 1; i <= n; i++) {
  134.  
  135. 		for (int j = 0; j < 26; j++) pre[j][i] = pre[j][i - 1] + (j == (s[i] - 'a'));
  136.  
  137. 	}
  138.  
  139.  
  140.  
  141. 	fact[0] = 1;  //setting this to fact[0] =0 , solves the problem.
  142. 	for (int i = 1; i <= 1e5 + 10; i++) fact[i] = 1ll * i * fact[i - 1] % mod;
  143.  
  144.  
  145.  
  146.  
  147. 	for (int i = 0; i <= 1e5 + 10; i++) ifact[i] = inv(fact[i]);
  148.  
  149.  
  150. 	int q;
  151. 	cin >> q;
  152.  
  153. 	while (q--) {
  154.  
  155. 		mpp.clear();
  156. 		ev.clear();
  157. 		od.clear();
  158. 		int l, r;
  159. 		cin >> l >> r;
  160.  
  161.  
  162. 		for (int i = 0; i < 26; i++) {
  163.  
  164. 			int cnt = pre[i][r] - pre[i][l - 1];
  165.  
  166. 			if (cnt > 0) {
  167.  
  168. 				if (cnt & 1) {
  169.  
  170. 					od.insert(i);
  171. 					mpp[i] = cnt; ;
  172.  
  173. 				}
  174.  
  175. 				else {
  176.  
  177. 					ev.insert(i);
  178. 					mpp[i] = cnt; ;
  179. 				}
  180.  
  181.  
  182. 			}
  183.  
  184. 		}
  185.  
  186.  
  187. 		int len = 0;
  188.  
  189.  
  190.  
  191. 		for (auto t : ev) len += mpp[t] / 2;
  192. 		for (auto t : od) len += mpp[t] / 2;
  193.  
  194. 		ll ans = fact[len];
  195.  
  196.  
  197.  
  198. 		ans %= mod;
  199.  
  200. 		for (auto t : ev) {
  201.  
  202. 			int x = mpp[t] / 2;
  203.  
  204. 			ans = ans * ifact[x] % mod;
  205. 		}
  206.  
  207. 		for (auto t : od) {
  208.  
  209. 			int x = mpp[t] / 2; ;
  210.  
  211. 			ans = ans * ifact[x] % mod;
  212.  
  213. 		}
  214.  
  215.  
  216. 		int ocnt = (int)od.size(); 
  217.  
  218. 		if (ocnt) ans = ans * ocnt % mod;
  219.  
  220. 		cout << ans << endl;
  221.  
  222. 	}
  223.  
  224.  
  225.  
  226. 	return  0;;
  227.  
  228.  
  229. }
Success #stdin #stdout 0.15s 4740KB
comments (?)
stdin
copy 
amim
1
1 4


2 3
stdout
copy 
2
https://ideone.com/zCpfga
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!