[ create a new paste ] login | about

Link: http://codepad.org/1KUNHJpI    [ raw code | output | fork ]

C++, pasted on Jan 30:
#include<bits/stdc++.h>
using namespace std;
 
#define pb push_back
#define ll long long
#define maxn 1000005
#define fr(i,j,k) for(int i=j;i<k;i++)
#define f(n) fr(i,0,n)
#define f1(n) fr(i,1,n+1)
#define ms(i) memset(i,0,sizeof(i));
#define ms1(i) memset(i,-1,sizeof(i));
#define F first
#define S second
//const int mod = 998244353;
ll mul = 31;
ll mod = 1e9+7;
ll h[maxn];
ll p[maxn];

void build(string s){
    ll cur = 0;
    ll now = mul;
    p[0] = 1;
    f1((int)s.size()){
        p[i] = now;
        now *= mul;
        now %= mod;
    }
    for(int i = 1 ; i <= (int)s.size() ; i ++){
        cur *= mul;
        cur += (int)s[i-1];
        cur %= mod;
        h[i] = cur;
    }
}
ll get(int l,int r){
    ll ret = (h[r] - (h[l-1] * p[r - l + 1] % mod) + mod) % mod;
    return ret;
}
bool isprime(int x){
    int sq = (int)sqrt(x);
    for(int i = 2 ; i <= sq ; i++){
        if( x % sq == 0){
            return 0;
        }
    }
    return 1;
}
ll getprime(int bs){
    ll num = mod + rand() * 10;
    while(!isprime(num)){
        num++;
    }
    return num;
}
 
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    srand(time(NULL));
    //mul = getprime(2011748);
    //mod = getprime(910600415);
    string s, t;
    cin >> s;
    cin >> t;
    build(t);
    int c0 = 0, c1 = 0;
    for(auto i:s){
        if(i=='0')c0++;
        else c1++;
    }
    int ans = 0;
    for(int i = 1 ; i < (int)t.size()/c0 ; i++){
        int left = t.size() - c0 * i;
        if(left % c1)continue;
        int len0 = i;
        int len1 = left / c1;
        ll h0 = 0, h1 = 0;
        int f = 0;
        int last = 0 ;
        //cout << len0 <<' '<<len1<<'\n';
        for(auto j:s){
            if(j=='0'){
                if(h0 == 0){
                    h0 = get(last+1,last + len0);
                }
                else{
                    if(get(last + 1,last + len0)!=h0){
                        f = 1;
                        break;
                    }
                }
                last += len0;
            }
            else{
                if(h1 == 0){
                    h1 = get(last+1,last + len1);
                }
                else{
                    if(get(last + 1,last + len1)!=h1){
                        f = 1;
                        break;
                    }
                }
                last += len1;
            }
        }
        //cout << h0 <<' ' << h1 << '\n';
        if(!f&& (h1 != h0||len1 != len0) ){
            ans++;
        }
    }
    cout << ans << '\n';
}


Output:
1
2
3
Line 23: error: bits/stdc++.h: No such file or directory
Line 15: error: ISO C++ does not support 'long long'
compilation terminated due to -Wfatal-errors.


Create a new paste based on this one


Comments: