AGC035E Develop

淸梣ling · 2023-01-03 19:09:34 · 题解

Solution

其他题解基本都把思路写出来了，这里具体说一下 DP 如何转移。

考虑删除数字 x 时，会产生 x-2 和 x+k，考虑 x 向 x-2 和 x+k 连边，那么假设我们删除了一部分点集，这些点集中一定没有环，否则是删不完的（手玩一下就知道了）。此时就相当于求多少点集内不形成环。

观察一下连边的性质，x 到 x-2 的奇偶性没有变，那么我们选择对 k 分奇偶：

设 $f_{i,j}$ 为长度为 $i$ 的链，最后连续选择的一段长度为 $j$，转移方程： $$ f_{i,j} = f_{i-1,j-1}\ (j>1) \\\\ f_{i,0} = \sum_{j=0}^k f_{i,j} $$

我们像上面一样对齐，如果不看偶数向奇数连边，那么所有边都是向上连的，所以我们可以选择从上向下逐层添加节点，来进行 DP。层数就是 m=\lfloor \frac{n+k}{2} \rfloor。

观察上图，可以发现每个环的大小都是 k+2，这个性质很重要，环的大小固定，那么 DP 就简单很多。

我们设 f[i][j][q] 为遍历到第 i 层，从右边开始最长连续段为 j，从左边开始最长连续段为 q 的方案数。这里要注意，我们 DP 时，要保证左侧的最长链一定延伸到了右侧，同时偶数向奇数的连边只用来判断是否成环，最长连续段中是没有这种边的，也就是一直保证偶数向奇数的连边不会用上，所以只要保证左侧最长链小于 k+2，那么自然不会成环。

考虑新加入的一层的两个节点，分为三种情况：

两个节点都不选，此时左右两侧的最长连续段都清零，即：
f[i][0][0]=\sum_{j=0}^n \sum_{q=0}^{k+1} f[i-1][j][q]
左侧选，右侧不选，此时右侧最长链变为 0，如果左侧最长边不为 0，左侧最长链加一，否则因为左侧最长链延伸到右侧需要有一层同时选择两个节点，所以此时不成立，左侧最长链还是 0。同时要保证有左侧节点，观察上面的图，两个链错位了 (k-1)/2 位，所以最上面只有右侧点的有 (k-1)/2 层，也就是 k-1 个节点，那么此时可以得到转移方程：
2i \ge k+1 \begin{cases} \displaystyle f[i][0][q+1] = \sum_{j=0}^n \sum_{q=1}^{k+1} f[i-1][j][q] \\\\ \displaystyle f[i][0][0]=\sum_{j=0}^n f[i-1][j][0] \end{cases}
左侧不选，右侧选，此时左侧最长链变为 0，右侧最长链加一。我们一样需要保证有右侧节点，右侧节点一共有 \lfloor \frac n2 \rfloor 层，不应超过 n 个节点：
f[i][j+1][0] = \sum_{j=0}^n \sum_{q=0}^{k+1} f[i][j][q]\ (2i \le n)
两个节点都选，此时右侧最长链加一，对于左侧，可以继承之前的左侧最长链，长度为 q+1，也可以在这一层横着走到右边，继承右侧最长链，长度为 j+2，设 w=\max(q+1, j+2)，那么可以得到转移方程：
f[i][j+1][w] = \sum_{j=0}^n \sum_{q=0}^{k+1} f[i][j][q]\ (k+1 \le 2i \le n)

最后答案自然就是 \sum_{j=0}^n \sum_{q=0}^{k+1} f[m][j][q]，时间复杂度 O(nk^2)\ or\ O(n^2k)。

Code

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

typedef long long ll;
ll p;
int n,k;
ll f[200][200],g[200][200][200];

void work1()
{
    ll ans=0;
    int m=(n+k)/2;
    g[0][0][0]=1;
    for(int i=1; i<=m; i++)
    {
        // 都不选
        for(int j=0; j<=n; j++)
        for(int q=0; q<=k+1; q++)
        g[i][0][0]=(g[i][0][0]+g[i-1][j][q])%p;

        // 只选右
        if(i*2<=n)
        for(int j=0; j<=n; j++)
        for(int q=0; q<=k+1; q++)
        g[i][j+1][0]=(g[i][j+1][0]+g[i-1][j][q])%p;

        // 只选左
        if(i*2>=k+1)
        for(int j=0; j<=n; j++)
        {
            for(int q=1; q<=k+1; q++)
            g[i][0][q+1]=(g[i][0][q+1]+g[i-1][j][q])%p;
            g[i][0][0]=(g[i][0][0]+g[i-1][j][0])%p;
            // 特判只有一个点，此时没用，当成0个点
        }

        // 左右都选
        if(i*2>=k+1&&i*2<=n)
        for(int j=0; j<=n&&j+1<=k+1; j++)
        for(int q=0; q<=k+1; q++)
        g[i][j+1][max(q+1, j+2)]=(g[i][j+1][max(q+1, j+2)]+g[i-1][j][q])%p;
    }

    for(int i=0; i<=n; i++)
    for(int j=0; j<=k+1; j++)
    ans=(ans+g[m][i][j])%p;
    cout<<ans;
}
void work2()
{
    ll sum1=0,sum2=0;
    f[0][0]=1; k/=2;
    for(int i=1; i<=n; i++)
    for(int j=0; j<=k; j++)
    {
        f[i][0]=(f[i][0]+f[i-1][j])%p;
        if(j) f[i][j]=(f[i][j]+f[i-1][j-1])%p;
    }
    for(int i=0; i<=k; i++)
    {
        sum1=(sum1+f[n/2][i])%p;
        sum2=(sum2+f[(n+1)/2][i])%p;
    }
    cout<<sum1*sum2%p;
}
int main()
{
    cin>>n>>k>>p;
    if(k&1) work1();
    else work2();
    return 0;
}