Submission #857382

---

Source Code Expand

#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define PB push_back
#define MP make_pair
#define MOD 1000000007LL
#define endl "\n"
const ll UNDEF = -1;
const ll INF=1e18;
template<typename T> inline bool chkmax(T &aa, T bb) { return aa < bb ? aa = bb, true : false; }
template<typename T> inline bool chkmin(T &aa, T bb) { return aa > bb ? aa = bb, true : false; }
template<class T> T extgcd(T a, T b, T& x, T& y) { for (T u = y = 1, v = x = 0; a;) { T q = b / a; swap(x -= q * u, u); swap(y -= q * v, v); swap(b -= q * a, a); } return b; }
template<class T> T mod_inv(T a, T m) { T x, y; extgcd(a, m, x, y); return (m + x % m) % m; }
ll mod_pow(ll a, ll n, ll mod) { ll ret = 1; ll p = a % mod; while (n) { if (n & 1) ret = ret * p % mod; p = p * p % mod; n >>= 1; } return ret; }
const ll mn=5e5+4;
const ll p=101;
ll ht[mn];
ll add(ll x, ll y) {return (x+y+MOD)%MOD;}
ll mul(ll x, ll y) {return (x*y)%MOD;}
ll gethash(ll x, ll y) {
	return mul(add(ht[y],-ht[x]),mod_inv(mod_pow(p,x,MOD),MOD));;
}
ll geom(ll x, ll n) {
	ll num=add(1,-mod_pow(x,n+1,MOD));
	ll den=add(1,-x);
	return mul(num,mod_inv(den,MOD));
}
ll powup(ll small, ll num, ll len) {
	return mul(small,geom(mod_pow(p,len,MOD),num-1));
}
bool isgood(ll x, ll y) {
	ll k=y-x;
	set<ll> divs;
	ll dlim=sqrt(k)+1;
	dlim=min(dlim,k);
	for (ll d=1;d<=dlim;d++) {
		if (k%d==0) {
			divs.insert(d);divs.insert(k/d);
		}
	}
	ll actual=gethash(x,y);
	for (auto &d:divs) {
		if(d==k) continue;
		ll small=gethash(x,x+d);
		ll num=k/d;
		ll len=d;
		ll big=powup(small, num, len);
		if (big==actual) {
			//printf("num:%lld len:%lld small:%lld big:%lld actual:%lld x:%lld x+d:%lld\n",num,len,small,big,actual,x,x+d);
			return false;
		}
	}
	return true;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	string s; cin>>s;
	ll n=s.length();
	ll h=0;
	ht[0]=h;
	ll m=1;
	for (ll x=0;x<n;x++) {
		h+=((s[x]-'a'+1)*m);
		h%=MOD;
		//printf("x:%lld h:%lld\n",x+1,h);
		ht[x+1]=h;
		m=(m*p)%MOD;
	}
	bool same=true;
	for (ll x=1;x<n;x++) {
		if (s[x]!=s[0]) same=false;
	}
	if (same) {
		printf("%lld\n1\n",n);
	}
	else if (isgood(0,n)) {
		printf("1\n1\n");
	}
	else {
		ll ans=0;
		for (ll x=1;x<n;x++) {
			if (isgood(0,x)&&isgood(x,n)) {
				ans++;
			}
		}
		printf("2\n%lld\n",ans);
	}
}

Submission Info

Judge Result