Submission #857574


Source Code Expand

Copy
#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; }
ll mod_pow(ll a, ll n) {
	ll ret = 1; ll p = a % MOD; while (n) { if (n & 1) ret = ret * p % MOD; p = p * p % MOD; n >>= 1; } return ret; 
}
inline ll mod_inv(ll a) {
	return mod_pow(a,MOD-2);
}
const ll mn=5e5+4;
const ll mnd2=mn/2;
const ll p=101;
ll ht[mn];
ll deninv[mn];
ll ppow[mn];
ll ppowinv[mn];
inline ll add(ll x, ll y) {return (x+y+MOD)%MOD;}
inline ll mul(ll x, ll y) {return (x*y)%MOD;}
inline ll gethash(ll x, ll y) {
	return mul(add(ht[y],-ht[x]),ppowinv[x]);;
}
inline ll geom(ll n, ll len) {
	ll num=add(1,-ppow[len*n]);
	return mul(num,deninv[len]);
}
inline ll powup(ll small, ll num, ll len) {
	return mul(small,geom(num,len));
}
bool isgood(ll x, ll y, ll d) {
	ll k=y-x;
	ll actual=gethash(x,y);
	{
		//printf("k:%lld d:%lld\n",k,d);
		//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) {
			return false;
		}
	}
	return true;
}
ll vans[mn];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	{
		ll t=1;
		for (ll x=0;x<mn;x++) {
			ppow[x]=t;
			deninv[x]=mod_inv(add(1,-t));
			ppowinv[x]=mod_inv(t);
			t=(t*p)%MOD;
		}
	}
	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 {
		for (ll x=1;x<=n;x++) vans[x]=1;
		for (ll d=1;d<=n/2;d++) {
			for (ll y=d*2;y<=n;y+=d) {
				if (!isgood(0,y,d)) vans[y]=0;
				if (y<n&&!isgood(n-y,n,d)) vans[n-y]=0;
			}
		}
		if (vans[n]) {
			printf("1\n1\n");
		}
		else {
			ll ans=0;
			for (ll x=1;x<n;x++) {
				ans+=vans[x];
			}
			printf("2\n%lld\n",ans);
		}
	}
}

Submission Info

Submission Time
Task F - Best Representation
User LiChenKoh
Language C++14 (GCC 5.4.1)
Score 900
Code Size 2315 Byte
Status AC
Exec Time 1086 ms
Memory 20380 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 400 / 400 500 / 500
Status
AC × 3
AC × 36
AC × 65
Set Name Test Cases
Sample example_01.txt, example_02.txt, example_03.txt
Subtask1 example_01.txt, example_02.txt, example_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt
All example_01.txt, example_02.txt, example_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt, subtask2_29.txt
Case Name Status Exec Time Memory
example_01.txt AC 332 ms 12032 KB
example_02.txt AC 333 ms 12032 KB
example_03.txt AC 332 ms 12032 KB
subtask1_01.txt AC 333 ms 12032 KB
subtask1_02.txt AC 333 ms 12032 KB
subtask1_03.txt AC 333 ms 12032 KB
subtask1_04.txt AC 333 ms 12032 KB
subtask1_05.txt AC 335 ms 12032 KB
subtask1_06.txt AC 335 ms 12032 KB
subtask1_07.txt AC 333 ms 12032 KB
subtask1_08.txt AC 336 ms 12032 KB
subtask1_09.txt AC 336 ms 12032 KB
subtask1_10.txt AC 335 ms 12032 KB
subtask1_11.txt AC 336 ms 12032 KB
subtask1_12.txt AC 336 ms 12032 KB
subtask1_13.txt AC 336 ms 12032 KB
subtask1_14.txt AC 336 ms 12032 KB
subtask1_15.txt AC 333 ms 12032 KB
subtask1_16.txt AC 332 ms 12032 KB
subtask1_17.txt AC 333 ms 12032 KB
subtask1_18.txt AC 333 ms 12032 KB
subtask1_19.txt AC 335 ms 12032 KB
subtask1_20.txt AC 336 ms 12032 KB
subtask1_21.txt AC 336 ms 12032 KB
subtask1_22.txt AC 335 ms 12032 KB
subtask1_23.txt AC 334 ms 12032 KB
subtask1_24.txt AC 335 ms 12032 KB
subtask1_25.txt AC 337 ms 12032 KB
subtask1_26.txt AC 336 ms 12032 KB
subtask1_27.txt AC 335 ms 12032 KB
subtask1_28.txt AC 336 ms 12032 KB
subtask1_29.txt AC 335 ms 12032 KB
subtask1_30.txt AC 335 ms 12032 KB
subtask1_31.txt AC 335 ms 12032 KB
subtask1_32.txt AC 335 ms 12032 KB
subtask1_33.txt AC 336 ms 12032 KB
subtask2_01.txt AC 894 ms 18580 KB
subtask2_02.txt AC 349 ms 16540 KB
subtask2_03.txt AC 1086 ms 20380 KB
subtask2_04.txt AC 1076 ms 20380 KB
subtask2_05.txt AC 349 ms 16540 KB
subtask2_06.txt AC 1081 ms 20380 KB
subtask2_07.txt AC 1079 ms 20380 KB
subtask2_08.txt AC 1038 ms 20380 KB
subtask2_09.txt AC 1036 ms 20380 KB
subtask2_10.txt AC 1042 ms 20380 KB
subtask2_11.txt AC 1035 ms 20380 KB
subtask2_12.txt AC 1037 ms 20380 KB
subtask2_13.txt AC 1086 ms 20380 KB
subtask2_14.txt AC 1084 ms 20380 KB
subtask2_15.txt AC 1069 ms 20380 KB
subtask2_16.txt AC 1066 ms 20380 KB
subtask2_17.txt AC 1085 ms 20380 KB
subtask2_18.txt AC 1086 ms 20380 KB
subtask2_19.txt AC 1055 ms 20380 KB
subtask2_20.txt AC 1043 ms 20380 KB
subtask2_21.txt AC 982 ms 19740 KB
subtask2_22.txt AC 1042 ms 20380 KB
subtask2_23.txt AC 1037 ms 20380 KB
subtask2_24.txt AC 915 ms 19100 KB
subtask2_25.txt AC 979 ms 19484 KB
subtask2_26.txt AC 1056 ms 19996 KB
subtask2_27.txt AC 904 ms 18844 KB
subtask2_28.txt AC 681 ms 16404 KB
subtask2_29.txt AC 875 ms 18588 KB