CF1811G2题解

ncwzdlsd · 2023-10-26 08:44:14 · 题解

序列问题，考虑 DP。

设计状态 f(i,j) 表示当前选了 i 个点，最后一个点颜色为 j 的方案数。

当 a_i\bmod k=1 时，该点的颜色可以任意选择，否则必须跟上一个点颜色相同。对于每个点，我们考虑它的不同颜色转移即可。

注意到对于 a_i\bmod k=1 的点，它的转移会退化成 O(n^3) 的。我们用 g_i 记录第 i 个完整的段的方案数即可优化转移。

注意转移时要从大到小枚举子序列长度，否则可能会出现小长度的答案重复更新大长度答案的情况。

维护两个标记：

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int mod=1e9+7,maxn=5005;
int c[maxn],g[maxn],f[maxn][maxn];
bool c2[maxn][maxn],c1[maxn];

void solve()
{
    int n,k;cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>c[i],g[i]=0,c1[i]=0;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=0,c2[i][j]=0;
    f[0][0]=1,g[0]=1,c2[0][0]=1,c1[0]=1;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j;j--)
        {
            if(j%k==1)
            {
                if(c1[j/k]) c2[j][c[i]]=1,f[j][c[i]]+=g[j/k],f[j][c[i]]%=mod;
            }
            else if(c2[j-1][c[i]]) c2[j][c[i]]=1,f[j][c[i]]+=f[j-1][c[i]],f[j][c[i]]%=mod;
            if(!(j%k)&&c2[j][c[i]]) c1[j/k]=1,g[j/k]+=f[j-1][c[i]],g[j/k]%=mod;
        }
    for(int i=n/k;i>=0;i--) if(c1[i]) {cout<<g[i]<<'\n';break;}
}

signed main()
{
    int t;cin>>t;
    while(t--) solve();
    return 0;
}