PA 2021 Od deski do deski

Semsue · 2022-06-21 12:20:47 · 题解

题意

对于一个长度为 n 的序列 A_1,A_2,\dots, A_n 每次你可以选择两个值相同但位置不同的元素 A_i,A_j，然后将 A_i,A_{i+1},\dots, A_j 删除.

如果一个序列可以通过上述操作删为空序列，那么就称这个序列是好的。

问有多少长度为 n 且元素在 [1,m] 内的好的序列.

1\le n\le 3000,1\le m\le 10^9.

题解

如果有包含关系的那么肯定删那个更大的，于是删除的区间不会有交。

考虑一个序列 S，如果 S+x 是 合法的，那么 S+x+x 也必然是合法的。于是可以考虑 dp，设 f_{i,j,1/0} 代表长度为 i 的序列，在后面放 j 种数可以变成合法的，当前是否合法。答案显然为 \sum f_{n,i,1}。

考虑如何转移，如果当前合法，那么继续填那 j 种显然会继续合法，并且合法数量不会增多。于是 f_{i,j,1}\times j\to f_{i+1,j,1}。如果填剩下的 m-j 种数中的某个，显然不合法了且会多出来一种你填的这个可以消掉变成合法的，于是 f_{i,j,1}\times (m-j)\to f_{i+1,j+1,0}。如果当前不合法，显然还是可以转移到合法 f_{i,j,0}\times j\to f_{i+1,j,1}。然后考虑第二种转移，和前面唯一的区别是，你如果再选一遍你当前选的，你还是寄。也就是你只能这么转移 f_{i,j,0}\times (m-j)\to f_{i+1,j,0}。

总结一下四种转移：

思考一下发现 i 个数的时候最多 i 种合法的，所以时空复杂度均为 O(n^2)。

int main(){
    cin>>n>>m;
    f[0][0][1]=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<=i;j++){
            if(f[i][j][1]){
                f[i+1][j][1]=add(f[i+1][j][1],mul(f[i][j][1],j));
                f[i+1][j+1][0]=add(f[i+1][j+1][0],mul(f[i][j][1],dec(m,j)));
            }
            if(f[i][j][0]){
                f[i+1][j][1]=add(f[i+1][j][1],mul(f[i][j][0],j));
                f[i+1][j][0]=add(f[i+1][j][0],mul(f[i][j][0],dec(m,j)));
            }
        }
    }
    for(int i=0;i<=n;i++)ans=add(ans,f[n][i][1]);
    cout<<ans;
    return 0;
}

2023/6/21 修改了错别字。