Submission #50473785

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
ll read(){ll r;scanf("%lld",&r);return r;}
const int N=500000;
char s[N+10];
vector<int> ch[N+10];
int subcycle(const string&t){
  int sz=t.size();
  for(auto i:ch[sz]) {
    assert(i < sz and sz%i == 0);
    bool cycle = true;
    rep(j,0,sz) if(t[j] != t[j%i]) {cycle = false;};
    if(cycle) return i;
  }
  return t.size();
}
template<class T>
T reverse(const T &a){
  int sz=size(a);
  T ret;
  rep(i,0,sz) ret.push_back(a[sz-1-i]);
  return ret;
}

vector<bool> cut(const string&t){ // [sz-1] = 是否 最小循环长度==长度
  int sz=t.size();
  assert(sz>=2);
  vector<int> cyc(sz,0); // cyc[长度]=最小循环节
  iota(begin(cyc),end(cyc),1);
  rep(i,1,sz) {
    for(int l:ch[i+1]) {
      if(l == cyc[i-l]){// 需要 l % cyc[i-l], 但是如果 cyc[i-l] 更小且 下面相等，那么应该有更小的周期
        bool ok = true;
        rep(j,0,l) if(t[j] != t[i+1-l+j]) {
          ok = false;
          break;
        }
        if(ok) {
          cyc[i]=l;
          break;
        }
      }
    }
  }
  vector<bool> ret(sz,0); // ret[长度]=最小循环节
  rep(i,0,sz) ret[i] = cyc[i]==i+1;
  return ret;
}

int main(){
  rep(i,1,N+1) rep(j,2,N+1) {
    if(i*j > N) break;
    ch[i*j].push_back(i);
  }
  scanf("%s",s);
  int sz = strlen(s);
  if(sz == 1) {
    printf("1\n1\n");
    return 0;
  }
  string s0;
  rep(i,0,sz) s0.push_back(s[i]);
  int i = subcycle(s0);
  if(i == sz) {
    printf("1\n1\n");
  }else if(i == 1) {
    printf("%d\n1\n",sz);
  }else{
    if(sz/i > 2) {
      int ways = (sz/i-2)*(i-1); // 中间的非两段
      for(auto w:cut(s0.substr(0,i))) ways+=w;
      for(auto w:cut(reverse(s0.substr(sz-i,i)))) ways+=w;
      printf("2\n%d\n",ways-2); // 刚好等于的时候
    }else{
      int ways = 0; // 只能切成2段
      auto w0 = cut(s0);
      auto w1 = reverse(cut(reverse(s0)));
      rep(i,0,sz-1) ways += w0[i] and w1[i+1];
      printf("2\n%d\n",ways);
    }
  }
  return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘ll read()’:
Main.cpp:5:21: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
    5 | ll read(){ll r;scanf("%lld",&r);return r;}
      |                ~~~~~^~~~~~~~~~~
Main.cpp: In function ‘int main()’:
Main.cpp:57:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   57 |   scanf("%s",s);
      |   ~~~~~^~~~~~~~

Judge Result