算法

讨论某个状态\((x,y)\)是否可达，\(x\)是狐狸到达的石头，\(y\)是猫的。

说，如果满足以下条件，那么它就是可到达状态：

\(t[0..y]\)不是\(s[0..x-1]\)的子串。

\(s[0..x]\)不是\(t[0..y-1]\)的字串。

\(s\)和\(t\)串的形式不能是这样的：\(s=......ab,t=......ba\)。

第三个条件很容易忽略！

建议多看几次rng_58的题解，我觉得题解思考的方式很新奇Orz：

考虑非常显然的必要条件

考虑如何通过必要条件来构造一个合法的序列

发现途中有必要条件忽略的情况！

完善条件，然后得出必要充分条件

代码

通过上面的分析，我们就可以乱搞了：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;typedef long long i64;template 
        
         void tension(T &a, const T &b) {    if (b < a) a = b;}const int MAXN = (int) 1e6 + 3;int n, m;char s[MAXN], t[MAXN];void init(char* const s, int n, char* const t, int m, int* const ret) {    for (int i = 1; i <= n; i ++) {        ret[i] = ret[i - 1] + 1;        while (ret[i] < m && t[ret[i]] != s[i])             ret[i] ++;        tension(ret[i], m);    }}int main() {    scanf("%s\n%s\n", s + 1, t + 1);    static int p1[MAXN], p2[MAXN];    n = strlen(s + 1);    m = strlen(t + 1);    init(s, n, t, m, p1);    init(t, m, s, n, p2);#define hash(x) (x == 'R' ? 0 : (x == 'G' ? 1 : 2))    static int sum[MAXN][3][3];    for (int i = 2; i <= m; i ++) {        for (int j = 0; j < 3; j ++)            for (int k = 0; k < 3; k ++) {                if (hash(t[i - 1]) == j && hash(t[i]) == k)                    sum[i][j][k] = sum[i - 1][j][k] + 1;                else                    sum[i][j][k] = sum[i - 1][j][k];            }    }    i64 ans = 0;    int L = 1;    for (int i = 1; i <= n; i ++) {        int R = p1[i];        while (L <= m && p2[L] < i) L ++;        ans += max(R - L + 1, 0);        if (L <= R && i > 1) {            int j = hash(s[i - 1]);            int k = hash(s[i]);            if (j != k) {                ans -= sum[R][k][j];                ans += sum[L - 1][k][j];            }        }    }    cout << ans << endl;    return 0;}