Znzryb's Blog
0%

Codeforces Round 1083 (Div. 2)——CF-2205-E. Simons and Dividing the Rhythm（分析分段 rev 操作的方法即 \text{rev}(XY) = \text{rev}(Y)\text{rev}(X)）

Posted on Edited on

题目大意

题目描述

给定一个长度为 nn 的目标数组 TT。

现有一个与 TT 等长的初始数组 SS，对 SS 进行恰好一次如下操作：
选择一个整数 kk，并将数组 SS 划分为 kk 个连续且不重叠的子段。假设这 kk 个子段的下标区间依次为 [l1,r1],[l2,r2],…,[lk,rk][l_1, r_1], [l_2, r_2], \dots, [l_k, r_k]，满足 l1=1l_1=1，rk=nr_k=n，且对于所有的 1≤i≤k−11 \le i \le k-1，都有 ri+1=li+1r_i + 1 = l_{i+1}。
然后，对这 kk 个子段分别独立地进行翻转操作。

即，选择的区间形如：

image

请求出有多少种不同的初始数组 SS，可以通过上述操作变为目标数组 TT。由于答案可能很大，请输出其对 998244353998244353 取模后的结果。

输入格式

第一行包含一个整数 tt（1≤t≤80001 \le t \le 8000），表示测试用例的数量。
每组测试用例的第一行包含一个整数 nn（1≤n≤80001 \le n \le 8000），表示数组的长度。
第二行包含 nn 个整数 T1,T2,…,TnT_1, T_2, \dots, T_n（1≤Ti≤80001 \le T_i \le 8000），表示目标数组 TT 的元素。
保证所有测试用例中 nn 的总和不超过 80008000。

输出格式

对于每组测试用例，输出一个整数，表示满足条件的数组 SS 的数量对 998244353998244353 取模后的结果。

样例输入

1
2
3
4
5
6
7
8
9
10
11
5
4
1 1 2 1
4
1 2 3 1
6
1 3 2 3 3 2
10
2 3 1 4 3 1 4 3 1 2
1
8000

样例输出

1
2
3
4
5
4
7
22
383
1

样例解释

在第一组测试用例中，T=[1,1,2,1]T = [1, 1, 2, 1]，以下 44 种数组 SS 可以被转换为 TT：

  • 对于 S=[2,1,1,1]S = [2, 1, 1, 1]，可以选择区间 [1,3][1, 3] 和 [4,4][4, 4] 进行翻转。翻转后数组变为 [1,1,2,1][1, 1, 2, 1]，等于 TT。

  • 对于 S=[1,2,1,1]S = [1, 2, 1, 1]，可以选择区间 [1,4][1, 4] 进行翻转。

  • 对于 S=[1,1,2,1]S = [1, 1, 2, 1]，可以选择区间 [1,2][1, 2]、[3,3][3, 3] 和 [4,4][4, 4] 进行翻转。

  • 对于 S=[1,1,1,2]S = [1, 1, 1, 2]，可以选择区间 [1,2][1, 2] 和 [3,4][3, 4] 进行翻转。

在第二组测试用例中，T=[1,2,3,1]T = [1, 2, 3, 1]，以下 77 种数组 SS 可以被转换为 TT：

  • 对于 S=[1,1,3,2]S = [1, 1, 3, 2]，可以选择区间 [1,1][1, 1] 和 [2,4][2, 4] 进行翻转。

  • 对于 S=[1,2,1,3]S = [1, 2, 1, 3]，可以选择区间 [1,1][1, 1]、[2,2][2, 2] 和 [3,4][3, 4] 进行翻转。

  • 对于 S=[1,2,3,1]S = [1, 2, 3, 1]，可以选择区间 [1,1][1, 1]、[2,2][2, 2]、[3,3][3, 3] 和 [4,4][4, 4] 进行翻转。

  • 对于 S=[1,3,2,1]S = [1, 3, 2, 1]，可以选择区间 [1,4][1, 4] 进行翻转。

  • 对于 S=[2,1,1,3]S = [2, 1, 1, 3]，可以选择区间 [1,2][1, 2] 和 [3,4][3, 4] 进行翻转。

  • 对于 S=[2,1,3,1]S = [2, 1, 3, 1]，可以选择区间 [1,2][1, 2]、[3,3][3, 3] 和 [4,4][4, 4] 进行翻转。

  • 对于 S=[3,2,1,1]S = [3, 2, 1, 1]，可以选择区间 [1,3][1, 3] 和 [4,4][4, 4] 进行翻转。

思路讲解

分析 rev 操作的一个重要公式是：

rev(XY)=rev(Y)rev(X)\text{rev}(XY) = \text{rev}(Y)\text{rev}(X)

可以继续拓展：

image

image

所以，我们要求转移时前缀相同，只采用这一后缀，即可得到独特的计数。

具体来讲，我们对这一后缀的要求是（在前缀相同的情况下）这一后缀无论如何划分，都达不到整体的效果。

1
rev(S) != rev(任意对S的划分方法)

比如说 [1, 2, 3, 4] 任何其他划分方式都达不到 rev([1, 2, 3, 4]) 的效果。

image

image

image

image

不过上面，opus4.6 给出的解释实际上不是很令人满意，因为带有非常明显的知道答案，凑出证明的痕迹。我们采用一种更加好的方法？（可能没有那么严谨，但是实际上是严谨的）

image

P4391 [BalticOI 2009] Radio Transmission 无线传输

我们不难发现，可以这种所谓的查找目标 C=C′C=C'，其实就是查找周期，其实和查找周期的哈希实现一模一样（详见上面一道题目）。

image

相信看了我的这个解释，应该都能看出来这个东西。

其实，形如 rev(S)=rev(ABA)rev(S)=rev(ABA)，其实是唯一一种形式，可以保证分段反转等于整体反转。

不过快速检查一个字符串是否有真前后缀相同，显然是使用 kmp（前缀数组，前缀数组就是这么定义的，能不好吗？） 还是比较好的，使用字符串哈希时间复杂度不是很优秀。

P3375 【模板】KMP（前缀函数）

好，现在问题就来到了，我们怎么样求 s[l;r]s[l;r] 是否有这个真前后缀匹配情况？

image

哈哈，其实解决这个问题的方法也很简单，那么就是跑 n 遍 kmp 就可以了，这道题目不是 O(n2)O(n^2) 的嘛。绷不住了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<ll> kmp(ll N,const vector<ll> &A){	// 返回总前缀数组pi
    vector<ll> pi(N+2);
    for(int i=2;i<=N;++i){
        ll len=pi[i-1];
        // if(S[i]==S[len+1]){
        // pi[i]=len+1;
        // }
        while(true){
            if(A[i]==A[len+1]){
                pi[i]=len+1;
                break;
            }
            if(len==0) break;
            len=pi[len];
        }
    }
    return pi;
}

最后的这个 dp 代码：

1
2
3
4
5
6
7
8
9
10
11
for (int l=1;l<=N;++l) {
    vector<ll> pi=kmp(N-l+1,vector<ll>(A.begin()+l-1,A.end()));
    ll offset=l-1;
    for (int r=l;r<=N;++r) {
        if (pi[r-offset]>0) {
            continue;
        }
        dp[r]+=dp[l-1];
        dp[r]%=mod;
    }
}

AC代码

AC
https://codeforces.com/contest/2205/submission/365177121

这个代码跑的好快啊，竟然

心路历程（WA，TLE，MLE……）

要好好想清楚这个 dp 是从哪里转移过来的，是从 l-1 转移过来的。

1
2
3
4
5
6
7
8
9
10
11
for (int l=1;l<=N;++l) {
    vector<ll> pi=kmp(N-l+1,vector<ll>(A.begin()+l-1,A.end()));
    ll offset=l-1;
    for (int r=l;r<=N;++r) {
        if (pi[r-offset]>0) {
            continue;
        }
        dp[r]+=dp[l-1];
        dp[r]%=mod;
    }
}

下面是废掉的 AI 提示

P4391 [BalticOI 2009] Radio Transmission 无线传输

计算这个串的周期所使用的这个哈希做法。

首先呢，计数问题，还是要选择 dp 解决。

不过总体上来说，我们对 border 的概念不是很熟。

确实，这道题目的难点就在于，对于不同的划分，如果有相同的这个答案怎么办？这个时候就需要引入字符串算法。

众所周知，计数题目，必须要找到一种方法，一种特征，保证符合这一特征的划分方式/方案之间是独立，互不相同的。这道题目的特征如下：（注意，我们认为单一字符符合这个要求，毕竟递归需要有一终止条件嘛）

image

只要有前后缀相同情况，那么一定会有更加细粒度的切分方法，实现相同效果。

不过，如果只是需要无前后缀相同情况的话，那么直接判断一下前后缀第一个一不一样不就行了？事实上，我们要求，我们所选择的串，其所有子串（长度 ≥ 2）的前后缀都必须不同。