Atcoder arc060

發表於 更新於 分類於 ， Disqus： 文章字數： 915 所需閱讀時間 ≈ 3 分鐘
F(字符串)

F - Best Representation

给小写字母字符串S

问S能最少被切割成多少个(?)，使得每个子串都不能表示成循环节（ababa好，ababab坏）

有多少个方案 能 达到最小的切割数 mod 1e9+7

|S| 5e5

2s

256mb

我的思路

如果整个字符串是好的，那么答案为1,1

否则 整个字符串 如果是坏的，那么它可以表示成 字符串t的重复拼接

那么 最小循环节 长度如果 > 1,那么删去最后一个 是否是一个方案呢？？

1
2
3
[.....][.....][.....][.....][.....][.....]
[...][...][...][...][...][...][...][...]
                                        x

注意到这个两个数差为1,所以gcd(len)=1

而它们相互间 多个不同偏移量的对应相等，将会像gcd过程一样对位相等

所以不可能

所以 最小分割一定是2

所以问题变成了，整个字符串有多少个切割让 left right 都是好的

同样的， 只要不是最小切割的倍数即可

所以感觉就过了?

还是有一点点问题

1
2
3
111222111222
xx
  yyyyyyyyyy

对于S的最小循环节 内还是有可能有更小的 循环的存在的

判断也好判断，如果要长度len的 循环节长度是cycle，那么len-cycle的循环节的长度是cycle的因数，注意前缀后缀都要算

然而 https://atcoder.jp/contests/arc060/submissions/50471607

ACx63,WAx2

subtask1_03.txt 和 subtask2_01.txt 炸了

1
2
3
4
5
6
7
abaababaab  
len(s) = 10, cycle size = 5  
brute force = 8  
left cycle, right not cycle, [0,5][6,9]  
abaaba  
2  
9

这样的话虽然 baab是好的，但是左边是坏的且超过了单个循环节的长度

代码

https://atcoder.jp/contests/arc060/submissions/50473785

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#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;
}

总结

核心还是string 的自相似的一些性质

感觉 一定能切两段的证明，没有数学化掉，这个题解官方没有发布，感觉数学上 这题还不知道怎么搞

然后arc111+ 以后才有英文题解， 061~110 先跳过吧，没有反馈的训练还是不行，不知道洛谷有没有题解，之后再说