fork(1) download
copy 
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <map>
  5. #include <vector>
  6. #include <algorithm>
  7.  
  8. #define ll unsigned long long
  9. #define PB push_back
  10.  
  11. #define rep(i,n) for (int i = 0; i<n; i++)
  12. #define clr(x, y) memset(x, y, sizeof x)
  13.  
  14. #define MAX 2010
  15. #define MOD 1000000007
  16.  
  17. using namespace std;
  18.  
  19. char s[MAX];
  20. int freq[40];
  21.  
  22. vector <ll> primes;
  23. bool *isprime = new bool[MAX];
  24. bool *compute = new bool[MAX];
  25.  
  26. void sieve (){
  27. 	ll i, j;
  28.  
  29. 	for (i = 0; i<=MAX; i++) isprime[i] = true;
  30.  
  31. 	isprime[0] = isprime[1] = false;
  32. 	primes.PB (2);
  33. 	for (i = 4; i<=MAX; i += 2) isprime[i] = false;
  34.  
  35. 	for (i = 3; i<=MAX; i += 2){
  36. 		if (isprime[i]){
  37. 			primes.PB (i);
  38. 			for (j = i*i; j<MAX; j += i)
  39. 				isprime[j] = false;
  40. 		}
  41. 	}
  42. }
  43.  
  44. map<ll, int> eq;
  45. map<ll, int> :: iterator it;
  46.  
  47. void factors (int n, bool add){
  48. 	ll aux = n;
  49. 	int i = 0;
  50.  
  51. 	while (primes[i]*primes[i] <= n){
  52. 		if (aux%primes[i] == 0){
  53. 			while (aux%primes[i] == 0) {
  54. 				aux /= primes[i];
  55.  
  56. 				if(add) eq[primes[i]]++;
  57. 				else eq[primes[i]]--;
  58. 			}
  59. 		}
  60.  
  61. 		i++;
  62. 	}
  63.  
  64. 	if (aux > 1) {
  65. 		if(add) eq[aux]++;
  66. 		else eq[aux]--;
  67. 	}
  68. }
  69.  
  70. // computa o fatorial transformando em um numero primo
  71. void fatorial(int x, bool add){
  72. 	for(int i = 2; i<=x; i++) factors (i, add);
  73. }
  74.  
  75. ll mulmod(ll a, ll b, ll c){
  76. 	ll x = 0,y = a%c;
  77. 	while(b > 0){
  78. 		if(b%2 == 1) x = (x+y)%c;
  79. 		y = (y*2)%c;
  80. 		b /= 2;
  81. 	}
  82. 	return x%c;
  83. }
  84.  
  85. // (a ^ b) % c
  86. ll pow(ll a, ll b, ll c){
  87. 	ll x=1, y=a;
  88. 	while(b > 0){
  89. 		if(b%2LLU == 1) x = mulmod(x, y, c);
  90. 		y = mulmod(y, y, c);
  91. 		b /= 2LLU;
  92. 	}
  93. 	return x%c;
  94. }
  95.  
  96. int main (){
  97. 	// calculo dos numeros primos menores que 2*10^3
  98. 	sieve();
  99.  
  100. 	while(scanf("%s", s) != EOF){
  101. 		clr(freq, 0);
  102. 		eq.clear();
  103.  
  104. 		int sz = strlen(s);
  105.  
  106. 		// fatorial do tamanho da string que entrada
  107. 		// "true" indica que estou somando o expoente do fatorial
  108. 		fatorial(sz, true);
  109.  
  110. 		// calcula as repeticoes da letras
  111. 		for (int i = 0; i<sz; i++) freq[s[i] - 'A']++;
  112.  
  113. 		// para cada letra, calculo o fatorial de quantas vezes ela apareceu
  114. 		// "false" indica que estou removendo o expoente..
  115. 		for (int i = 0; i<29; i++) if(freq[i]) fatorial(freq[i], false);
  116.  
  117. 		ll ans = 1;
  118.  
  119. 		// uma "lista" com os numeros primos e seus expoentes.
  120. 		for(it = eq.begin(); it != eq.end(); it++){
  121. 			// a^b
  122. 			int a = it->first;
  123. 			int b = it->second;
  124.  
  125. 			ans = (ans * pow(a, b, MOD)) % 1000000007;
  126. 		}
  127.  
  128. 		printf("%llu\n", ans);
  129. 	}
  130.  
  131.  
  132. 	return 0;
  133. }
  134.  
Success #stdin #stdout 0s 3436KB
comments (?)
stdin
copy 
UFFS
QUIDESTVERITASESTVIRQUIADEST
stdout
copy 
12
610881623
https://ideone.com/SNZ9aQ
language:
C++ (gcc 8.3)
created:
9 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!