小清新记数题。
发现将两段合法的拼接起来计数会有很多重复，因为会有很多种消除方法。于是我们考虑对于一位以为计数，并且将合法性压入状态。
考虑怎样才能够合法。如果对于当前位置选择数字 $x$，需要存在之前的某个位置 $i$ 数字为 $x$，满足 $[1,i-1]$ 合法。前面有满足这样的与 $x$ 相等的都可以选。于是我们考虑将有多少不同的数满足该条件压入状态中。设计状态 $f(i,j),g(i,j)$ 分别表示有 $j$ 不同的数满足该条件，不合法与合法的方案数。
于是我们可以很好的进行转移。得到状态转移方程：
时间复杂度 $\mathcal O(n\log n)$。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include<iostream>
#include<cstdio>
using namespace std;
const int N=3e3+10,mod=1e9+7;
int n,m;
int f[N][N],g[N][N];
inline int adj(int x){return (x>=mod)?x-mod:x;}
int main()
{
scanf("%d %d",&n,&m);
f[1][1]=m;
for(int i=2;i<=n;i++)
for(int j=1;j<=min(n,m);j++)
{
f[i][j]=adj(f[i][j]+1ll*g[i-1][j-1]*(m-j+1)%mod);
f[i][j]=adj(f[i][j]+1ll*f[i-1][j]*(m-j)%mod);
g[i][j]=adj(g[i][j]+1ll*f[i-1][j]*j%mod);
g[i][j]=adj(g[i][j]+1ll*g[i-1][j]*j%mod);
}
int ans=0;
for(int i=1;i<=min(m,n);i++)ans=adj(ans+g[n][i]);
printf("%d\n",ans);
return 0;
}
|