[DP记录]AT4169 [ARC100D] Colorful Sequences
command_block
2021-05-04 15:46:46
**题意** ： 给定一个长为 $m$ 的序列 $A$，保证每个数都 $\leq k$。
如果一个全部元素均 $\leq x$ 的序列中存在一个长度为 $x$ 连续区间，恰好是 $1\sim x$ 的排列，那么称这个序列为 「 $x$−好序列 」。
给定长度 $n$ 。求所有长度为 $n$ 的 「 $k$−好序列 」 共包含了多少个 $A$ （允许重叠）。
$n\leq 2.5\times 10^4,m\leq 400$ ，时限$\texttt{2s}$。
------------
发现对好序列计数较为困难（条件是或起来的），考虑取反，先统计在所有序列中 $A$ 的出现次数，再减去不好序列中 $A$ 的出现次数。
前者容易得到 ： 枚举 $A$ 的起点，确定了接下来的 $m$ 个，其余位置随意。为 $k^{n-m}(n-m+1)$。
下面是后者的计算。
- Case 1 : $A$ 本身是好序列。
包含 $A$ 的序列必然是好序列，答案为 $0$。
- Case 2 : $A$ 中没有重复的数。
由于没有重复的数，各个颜色之间并没有本质区别。 $A$ 为所有 “$m$ 个不同 $[1,k]$ 内数组成的序列” 的答案都是相同的。
于是，统计它们的和，并将答案除以 $k^{\underline m}$。
（定义一个区间是好的当且仅当其中没有重复的数）
记 $f[i,j]$ 表示填写了 $i$ 个数，且极长好后缀的长度为 $j$ 的方案数。
有转移 ：
$$
\begin{matrix}
f[i,j]\rightarrow f[i+1,k]&(1\leq k\leq j)\\
(k-j)f[i,j]\rightarrow f[i+1,j+1]
\end{matrix}
$$
第一条 ： 放一个和倒数第 $k$ 个重复的数。
第二条 ： 放一个前 $j$ 个没有出现过的数。这个数有 $k-j$ 种可能。
记 $g[i,j]$ 表示填写了 $i$ 个数，且极长好后缀的长度为 $j$ ，含有的长度为 $m$ 的好区间总数。
转移和 $f$ 相同，在 $j\geq m$ 时额外加上 $f[i,j]$。
答案即为 $\sum g[n,\_]/k^{\underline m}$。
- Case 2 : $A$ 中有重复的数。
记 $A$ 极长好前后缀的长度分别为 $L,R$。
枚举 $A$ 放置的位置的左端点 $p$ ，从 $A$ 分别向左向右考虑。
对于左侧，令 $f[0][L]=1$ ，然后 $\rm DP$ ， $\sum f[p-1][\_]$ 即为左侧的方案数。
对于右侧，令 $f[0][R]=1$ ，然后 $\rm DP$ ， $\sum f[n-m-p+1][\_]$ 即为右侧的方案数。
上述 $\rm DP$ 容易用前缀和优化做到 $O(nm)$ 。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 25050
#define MaxK 405
using namespace std;
const int mod=1000000007;
ll powM(ll a,int t=mod-2){
ll ret=1;
while(t){
if (t&1)ret=ret*a%mod;
a=a*a%mod;t>>=1;
}return ret;
}
int f[MaxN][MaxK],g[MaxN][MaxK];
int n,m,k,x[MaxN],e[MaxK],ans;
void solve1()
{
f[0][0]=1;f[1][1]=k;
for (int i=1;i<=n;i++){
for (int j=1;j<k;j++){
f[i][j]=(f[i][j]+f[i-1][j])%mod;
f[i+1][j+1]=1ll*(k-j)*f[i][j]%mod;
g[i][j]=(g[i][j]+g[i-1][j])%mod;
if (j>=m)g[i][j]=(g[i][j]+f[i][j])%mod;
g[i+1][j+1]=1ll*(k-j)*g[i][j]%mod;
}
f[i][k]=g[i][k]=0;
for (int j=k-1;j;j--){
f[i][j]=(f[i][j]+f[i][j+1])%mod;
g[i][j]=(g[i][j]+g[i][j+1])%mod;
}
}
int buf=1;
for (int i=0;i<m;i++)buf=1ll*buf*(k-i)%mod;
ans=1ll*powM(buf)*g[n][1]%mod;
}
void solve2()
{
int L=1,R=m;
for (int i=1;i<=k;i++)e[i]=0;
while(!e[x[L]])e[x[L++]]=1;L--;
for (int i=1;i<=k;i++)e[i]=0;
while(!e[x[R]])e[x[R--]]=1;R++;
R=m-R+1;
for (int i=0;i<=L;i++)f[0][i]=1;
for (int i=0;i<=R;i++)g[0][i]=1;
f[1][L+1]=k-L;g[1][R+1]=k-R;
for (int i=1;i<=n-m;i++){
for (int j=1;j<k;j++){
f[i][j]=(f[i][j]+f[i-1][j])%mod;
f[i+1][j+1]=1ll*(k-j)*f[i][j]%mod;
g[i][j]=(g[i][j]+g[i-1][j])%mod;
g[i+1][j+1]=1ll*(k-j)*g[i][j]%mod;
}
f[i][k]=g[i][k]=0;
for (int j=k-1;j;j--){
f[i][j]=(f[i][j]+f[i][j+1])%mod;
g[i][j]=(g[i][j]+g[i][j+1])%mod;
}
}
for (int p=1;p<=n-m+1;p++)
ans=(ans+1ll*f[p-1][1]*g[n-m-p+1][1])%mod;
}
int main()
{
scanf("%d%d%d",&n,&k,&m);
if (k>n){puts("0");return 0;}
bool fl1=0,fl2=0;
for (int i=1,tl=0;i<=m;i++){
scanf("%d",&x[i]);
tl=max(tl,e[x[i]]);e[x[i]]=i;
if (i-tl==k)fl1=1;
if (tl>0)fl2=1;
}
if (!fl1&&k<=n){
if (!fl2)solve1();
else solve2();
}
int buf=powM(k,n-m)*(n-m+1)%mod;
printf("%d",(buf-ans+mod)%mod);
return 0;
}
```