fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long int;
  4. #define inf 1000000000000000LL
  5. #define mod 1000000007LL
  6. #define FOR(i,a,b) for(int i = a; i < b; i++)
  7. const ll Mod = 1000000009LL;
  8. const ll Base = 271LL;
  9.  
  10. struct hashed_string{
  11.     private:
  12.     string s; ll n;
  13.     vector <ll> prefix;
  14.     vector <ll> pow;
  15.     public:
  16.     hashed_string(string a){
  17.         s = a; n = a.size();
  18.         prefix.assign(n, 0);
  19.         ll sum = 0;
  20.         pow.assign(n+1, 0);
  21.         pow[0] = 1;
  22.         for (int i = 1; i <= n; i++){
  23.             pow[i] = (pow[i-1] * Base) % Mod;
  24.         }
  25.         for (int i = 0; i < n; i++){
  26.             prefix[i] = ((sum * Base) % Mod + s[i] - 'a' + 1) % Mod;
  27.             sum = prefix[i];
  28.         }
  29.     }
  30.     ll get_hash(ll l, ll r){
  31.         ll x = prefix[r];
  32.         if (l >= 1){
  33.             l--;
  34.             x = ((x - prefix[l] * pow[r - l] % Mod) % Mod + Mod) % Mod;
  35.         }
  36.         return x;
  37.     }
  38. };
  39. void solve() {
  40.     string s1,s2;
  41.     cin >> s1 >> s2;
  42.     vector <ll> cnt(2,0);
  43.     for (int i = 0; i < s1.size(); i++){
  44.         cnt[s1[i] - '0'] += 1;
  45.     }  
  46.     if (cnt[0] < cnt[1]){
  47.         string sub;
  48.         for (int i =0; i < s1.size(); i++) sub += (s1[i] == '0' ? '1' : '0');
  49.         swap(cnt[0], cnt[1]);
  50.         s1 = sub;
  51.     }
  52.     hashed_string v(s2);
  53.     ll answ = 0;
  54.     ll n = s2.size();
  55.     for (int i = 1; i <= n; i++){
  56.         if (cnt[0] * i > n) break;
  57.         vector <ll> w(2, -1);
  58.         if (cnt[1] == 0) continue;
  59.         if ((n - cnt[0] * i) % cnt[1] != 0) continue;
  60.         ll x0 = i;
  61.         bool flag = true;
  62.         ll x1 = (n - cnt[0] * i) / cnt[1];
  63.         if (x1 == 0 || x0 == 0){
  64.             continue;
  65.         }
  66.         int p = 0;
  67.         for (int j = 0; j < n;){
  68.             if (s1[p] == '0'){
  69.                 if (v.get_hash(j, j + x0 - 1) != w[0] && w[0] != -1){
  70.                     flag = false;
  71.                     break;
  72.                 }   
  73.                 w[0] = v.get_hash(j, j + x0 - 1);
  74.                 j += x0;
  75.             }   
  76.             else{
  77.                 if (v.get_hash(j, j + x1 - 1) != w[1] && w[1] != -1){
  78.                     flag =false;
  79.                     break;
  80.                 }
  81.                 w[1] = v.get_hash(j, j + x1 - 1);
  82.                 j += x1;
  83.             }
  84.             p++;
  85.         }
  86.         if (flag && w[0] != w[1]) answ++;
  87.     }
  88.     cout << answ << "\n";
  89. }
  90.  
  91. int main() {
  92.     ios::sync_with_stdio(false);
  93.     cin.tie(nullptr);
  94.  
  95.     ll t = 1;
  96.     while (t--) {
  97.         solve();
  98.     }
  99.  
  100.     return 0;
  101. }
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/25VYxJ
language:
C++14 (clang 8.0)
created:
2 hours 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!