CF1515E Phoenix and Computers 题解

· · 题解

更好的阅读体验

感觉这样的 \text{dp} 题还比较多，思路都比较的神奇。

个人感觉比较像区间 \text{dp} 的一类变种。

但又和区间 \text{dp} 的维护方式极不一样。

对于此类 \text{dp}

这一类 \text{dp} 主要维护的是一个一个的块，可以理解成连通块。

将 f_{i,j} 看作放置 \text{i} 个元素，形成了 \text{j} 个块的方案数。

有三类操作。

将某个块的元素个数加一

那么每一个块都有可能加一。

所以。

f_{i,j}=f_{i-1,j}\times j

新增一个块

类似插空的思路。

原来有 j - 1 个块，所以有 \text{j} 个空。

f_{i,j}=f_{i-1,j-1}\times j

合并两个块

与第二点类似，但是不能在两边插空。

所以还是只有 \text{j} 个空。

f_{i,j}=f_{i-1,j+1}\times j

时间复杂度 O(n^2)。

这就是这一类问题的基本操作。

关于本题

我们发现，对于一般的 \text{dp} 而言，不怎么好去维护这个问题。

就可以考虑一下上面所说的 \text{dp}。

我们从小到大去给元素排位置。

还是从三种情况去讨论。

新增元素

可以发现，对于一个新增加的元素，有两种情况。

第一种是直接加入。

f_{i,j}=f_{i-1,j}\times j\times 2

第二种是隔一个加入，这样又会有一个自动生成，相当于加了两个。

f_{i,j}=f_{i-2,j}\times j\times 2

新增块

这种情况直接加就可以了。

f_{i,j}=f_{i-1,j-1}\times j

合并块

可以发现，合并两个块也有两种情况。

第一种是两个块中间空了两个格子，随便加上一个另一个也有了。

f_{i,j} = f_{i-2,j+1}\times 2\times j

第二种是两个块中间空了三个格子，这种情况加上中间的那个就可以连起来了。

f_{i,j}=f_{i-3,j+1}\times j

Code

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

int n , mod , f[410][410];

inline int read()
{
    int asd = 0 , qwe = 1; char zxc;
    while(!isdigit(zxc = getchar())) if(zxc == '-') qwe = -1;
    while(isdigit(zxc)) asd = asd * 10 + zxc - '0' , zxc = getchar();
    return asd * qwe;
}

signed main()
{
    n = read() , mod = read() , f[1][1] = 1;
    for(int i = 2;i <= n;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            f[i][j] += f[i - 1][j - 1] * j;
            f[i][j] += f[i - 1][j] * j * 2;
            f[i][j] += f[i - 2][j] * j * 2;
            if(i > 2) f[i][j] += f[i - 2][j + 1] * 2 * j;
            if(i > 3) f[i][j] += f[i - 3][j + 1] * j;
            f[i][j] %= mod;
        }
    }
    cout << f[n][1] << endl;
    return 0;
}