fork download
copy 
  1. #include<iostream>
  2. #include<cstring>
  3. #define debug(x) cerr << __LINE__ << " : "<<#x<<" is "<<x<<endl
  4.  
  5. using namespace std;
  6. typedef unsigned long long ull;
  7. const ull mod = 1e9 + 7; 
  8. const int N = 1e6 + 5;
  9. char s[100005],t[N];
  10. ull base[N],hash_val[N],hash0,hash1,hash_base = 7758258;
  11. int n,cnt0,cnt1,m,len[2];
  12. int main(){
  13.     ios::sync_with_stdio(false);
  14.     cin.tie(0);
  15.     cout.tie(0);
  16. 	cin >> (s + 1);
  17. 	cin >> (t + 1);
  18. 	n = strlen(s + 1);
  19. 	m = strlen(t + 1);
  20. 	base[0] = 1;
  21. 	for(int i = 1;i < N;i++){
  22. 		base[i] = base[i - 1] * hash_base;
  23. 	}
  24. 	for(int i = 1;i <= m;i++){
  25. 		hash_val[i] = hash_val[i - 1] * hash_base + t[i] - 'a';
  26. 	}
  27. 	for(int i = 1;i <= n;i++){
  28. 		if(s[i] == '0')
  29. 			cnt0++;
  30. 		else 
  31. 			cnt1++;
  32. 	}
  33.  
  34. 	ull ans = 0;
  35. 	for(int i = 1;i * cnt0 <= m - 1;i++){
  36.  
  37. 		if((m - i * cnt0) % cnt1 != 0)continue;
  38.  
  39. 		len[0] = i, len[1] = (m - i * cnt0) / cnt1;
  40. 		bool f0 = 0,f1 = 0,f = 1;
  41. 		for(int j = 1,idx = 1;j <= m;j += len[s[idx] == '1'],idx++){
  42.  
  43. 			int tmp_len = len[s[idx] == '1'];
  44. 			int tmp = tmp_len + j - 1;
  45. 			ull tmp_hash = hash_val[tmp] - hash_val[tmp - tmp_len] * base[tmp_len];
  46.  
  47. 			if(s[idx] == '0'){
  48. 				if(!f0)hash0 = tmp_hash,f0 = 1;
  49. 				else if(hash0 != tmp_hash){
  50. 					f = 0;
  51.  
  52. 					break;
  53. 				}
  54. 			}
  55. 			if(s[idx] == '1'){
  56. 				if(!f1)hash1 = tmp_hash,f1 = 1;
  57. 				else if(hash1 != tmp_hash){
  58. 					f = 0;
  59. 					break;
  60. 				}
  61. 			}
  62. 		}
  63. 		if(len[0] == len[1] && hash0 == hash1)continue;
  64. 		if(f)ans++;
  65. 	}
  66. 	cout << ans << '\n';
  67. 	return 0;
  68. }
Success #stdin #stdout 0.01s 11728KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/uMCrl7
language:
C++14 (gcc 8.3)
created:
7 days 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!