http://arc077.contest.atcoder.jp/tasks/arc077_d
実験的にやるのがたぶん正攻法だけど、もうちょっと文字列の周期のこととかに気を配れるとよかった。
解説にも書いてありますが、g(n+2)=g(n+1)+g(n)になります。これは実験をすると比較的簡単に気づけます。
証明は
g(n)→g(n+1)にするということは、g(n)の接頭辞と接尾辞で一致しているもののうち、文字数が最大のものをTとすると、
g(n+1)=g(n)*2-Tとなるので、g(n)=S*n+S'とすれば
g(n+1)=S*n+S'+S(T=S*(n-1)+S'より)
g(n+2)=(S*n+S'+S)+(S*n+S') (T=Sより)
=g(n+1)+g(n)となります。
g(0)=T*n+T'とすると、g(1)=T*n+T'+Tであり、MP法を使えばTは求められるので解けました。
副産物として文字列の長さをNとしてMP[N]=aならば最初のN-a文字が文字列の周期であることもわかりました。
気づいたは気づいたんだけど、証明をどうすればいいかわかりませんでした。
文字列は周期が重要ということを完全に忘れてましたね…。
int N; ll L, R; int A[MAX_N]; ll C[210][26]; ll D[210]; vector<int> MP(string S) { //it doesn't include itself int n = (int)S.size(); vector<int> A(n + 1); A[0] = -1; rep(i, 0, n) { int j = A[i]; while (j >= 0 && S[i] != S[j]) j = A[j]; j++; A[i + 1] = j; } return A; } vi calc1(ll n) { ll a = n / N; ll b = n % N; vector<ll> cnt1(26, 0); vector<ll> cnt2(26, 0); rep(i, 0, N) { if(i < b) cnt2[A[i]]++; cnt1[A[i]]++; } rep(i, 0, 26) cnt1[i] = cnt1[i] * a + cnt2[i]; return cnt1; } vi calc2(ll n, int m) { vector<ll> res(26, 0); for(int i = m - 1; i >= 0; i--) { if(n - D[i] >= 0) { n -= D[i]; rep(j, 0, 26) { res[j] += C[i][j]; } } } rep(i, 0, n) res[A[i]]++; return res; } void solve() { string str; cin >> str; N = sz(str) / 2; string tmp; rep(i, 0, N) tmp += str[i]; int a = MP(tmp)[N]; rep(i, 0, N) A[i] = str[i] - 'a'; cin >> L >> R; L--; if(a == 0) { vi lv = calc1(L); vi rv = calc1(R); rep(i, 0, 26) { rv[i] -= lv[i]; cout << rv[i] << " "; } cout << "\n"; } else { rep(i, 0, N) { C[0][A[i]]++; C[1][A[i]]++; if(i < N - a) C[1][A[i]]++; } D[0] = N; D[1] = 2 * N - a; int i = 0; for(i = 2; ; i++) { D[i] = D[i - 1] + D[i - 2]; rep(j, 0, 26) C[i][j] = C[i - 1][j] + C[i - 2][j]; if(D[i] >= R) break; } vi lv = calc2(L, i); vi rv = calc2(R, i); rep(i, 0, 26) { rv[i] -= lv[i]; cout << rv[i] << " "; } cout << "\n"; } }
