当前位置：首页 > news >正文

（计数）洛谷 P8386 PA2021 Od deski do deski/P10375 AHOI2024 计数题解

news 来源：原创 2025/5/19 23:43:18

题意

给定 $n$ ， $m$ ，求满足以下限制的长度为 $n$ 的序列数目：

每个元素在 $[1, m]$ 之间；
一次操作定义为删除一个长度至少为 $2$ 且区间两端相等的区间，该序列需要在若干次操作内被删空。

答案对 $10^9+7$ 取模。

$\le n \le 3000$ ， $\le m \le 10^9$ 。

思路

容易发现一个性质：对于一个序列 $S$ ，在后面加入 $x$ ，那么 $S$ 中第一次出现 $x$ 的位置直到末尾添加的 $x$ 都会被删去。

我们考虑对 $1\sim n$ 每一位填数字，我们发现填的数字是什么其实并不重要，因为我们要求的是序列数目而不是具体的序列种类。我们需要知道的是有多少种 $x$ 可以被添加到末尾。

根据上面的性质，我们可以知道一个可以被全部删除的序列长什么样子（下文称为合法的）：可以是首尾数字相同的序列 $S_0$ ，也可以是很多个不同的 $S_0$ 拼接而成的 $S$ ，它们都是合法的。

那我们考虑维护合法的和不合法的状态（不合法状态可以转移到合法的）。设 $f_{i,j,op}$ 表示前 $i$ 个数，出现了“有效的”数 $j$ 种，当前序列状态为 $o p$ 的方案数：

$o p = 0$ 表示该序列不合法，需要添加一个 $x$ 使之合法；
$o p = 1$ 表示该序列合法。

有效的是什么意思？是指后面可以添加的 $x$ 是这 $j$ 种数的一个，使之变成合法的序列（在这里要搞清楚这个定义，后面有一个状态转移和这个强相关才能理解）。

初始时当然是 $f_{1,1,0}=m$ ，可以填 $m$ 种数中的一个。

考虑转移：枚举当前数列长度 $i$ 和数的种类数 $j\le\min(i,m)$ ，此处考虑向后转移。

对于 $f_{i+1,j,1}$ ，可以从前 $i$ 个不合法的转移过来，填 $j$ 种数中的一个；合法亦然。有效数的量不变：
$\begin{matrix} f_{i+1,j,1}\leftarrow f_{i,j,1}\times j\\ f_{i+1,j,1}\leftarrow f_{i,j,0}\times j \end{matrix}$

对于前 $i + 1$ 个不合法的，可以是前 $i$ 个合法的，添加一个 $j$ 种数之外的数 $m - j$ 种，那么这个前 $i + 1$ 个不合法的序列的有效数有 $j + 1$ 个了：
$f_{i+1,j+1,0}\leftarrow f_{i,j,1}\times(m-j)$

也可以是前 $i$ 个不合法的转移过去，为了使这个长度为 $i + 1$ 的序列不合法，我们也要添加 $j$ 种数之外的数 $x^{'}$ ，可以有 $m - j$ 种。但是现在这个这个长度为 $i + 1$ 的不合法序列的有效颜色有多少呢？

我们发现这个 $x^{'}$ 不属于前 $i$ 个的 $j$ 种的任意一个，如果在这个这个长度为 $i + 1$ 的不合法序列后面再添加一个 $x^{'}$ ，是不能将其变成合法的。
在这里插入图片描述
因此有效数的种数并非 $j + 1$ ，而是 $j$ 。

最后答案就是 $\displaystyle\sum_{i=1}^{m}f_{n,i,1}$ 。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=3002,mod=1e9+7;
ll n,m;
ll f[N][N][2];
//前i个，出现了j种数，后面可以加j种颜色中的一个使之合法
//当前序列，0不合法1合法，的方案数 
//后面加的什么颜色不重要 
int main()
{scanf("%lld%lld",&n,&m);f[1][1][0]=m;for(ll i=1;i<n;i++){for(int j=1;j<=min(i,m);j++){f[i+1][j][1]=(f[i+1][j][1]+f[i][j][0]*j%mod)%mod;//后面加已经有的j种颜色 f[i+1][j][1]=(f[i+1][j][1]+f[i][j][1]*j%mod)%mod;//后面加已经有的j种颜色 f[i+1][j+1][0]=(f[i+1][j+1][0]+f[i][j][1]*(m-j)%mod)%mod;//后面加还没有的m-j种颜色 f[i+1][j][0]=(f[i+1][j][0]+f[i][j][0]*(m-j)%mod)%mod;//后面加还没有的m-j种颜色，不合法//但是在后面直接加这个新加的颜色，整段还是不合法//因此在后面只能加原来的j种颜色 }}ll ans=0;for(int i=1;i<=m;i++)ans=(ans+f[n][i][1])%mod;printf("%lld",ans);return 0;
}

题意

思路

代码

相关文章：