【题解】WF2012-Fibonacci Words

Posted on Edited on In Disqus:

题目

GYM101205D: https://codeforces.com/gym/101205/problem/D

UVA1282: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=247&page=show_problem&problem=3895

题意

\(F[0] = 0, F[1] = 1, F[n] = F[n - 1] + F[n - 2]\)，其中 \(+\) 是字符串连接。问给定 01 串在 \(f[n]\) 中的出现次数。

题解

  • 首先考虑 KMP。
  • 令 \(f[i][j]\) 表示第 \(j\) 个位置开始尝试匹配 \(F[i]\) 这个字符串的最终位置，\(g[i][j]\) 表示这个匹配过程中的成功次数。
  • 考虑一下加入字符 \(c\) 之后刚好匹配了整个串，那么成功次数 +1，而且下一个字符加入时一定会失配并回退匹配长度。
  • \(f\) 的转移类似于倍增，\(g\) 的计算就是考虑在串的前一部分 (\(F[i-1]\)) 和后一部分 (\(F[i - 2]\)) 的成功次数之和。

代码

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
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
// -----------------------------------------------------------------------------
const int N = 100 + 10, M = 1E5 + 100;

void get_pi(int a[], char s[], int n) {
    int j = a[0] = 0;
    FOR (i, 1, n) {
        while (j && s[i] != s[j]) j = a[j - 1];
        a[i] = j += s[i] == s[j];
    }
}

char s[M];
int a[M], m;

void go(LL x[], LL y[], char c) {
    FOR (i, 0, m + 1) {
        int p = i;
        while (p > 0 && s[p + 1] != c) p = a[p];
        x[i] = p + (s[p + 1] == c);
        y[i] = x[i] == m;
    }
}
LL g[N][M], f[N][M];

int main() {
    int n, Ca = 0;
    while (cin >> n) {
        scanf("%s", s + 1);
        m = strlen(s + 1);
        get_pi(a + 1, s + 1, m);
        go(f[0], g[0], '0'); go(f[1], g[1], '1');
        FOR (i, 2, n + 1)
            FOR (j, 0, m + 1) {
                f[i][j] = f[i - 2][f[i - 1][j]];
                g[i][j] = g[i - 1][j] + g[i - 2][f[i - 1][j]];
            }
        printf("Case %d: %lld\n", ++Ca, g[n][0]);
    }
}