[PA2021] Od deski do deski 题解

T1 [PA2021] Od deski do deski

发现合法的字符串一定是类似 \(\texttt{aa...aabb...bbcc...cc}\) 的形式，也就是若干个 \(\texttt a\)、若干个 \(\texttt b\) 和若干个 \(\texttt c\) 等组成的形式。如果当前选好的串 \(S_1\) 是合法的，且有另一个合法的串 \(S_2\)，那么显然 \(S_1+S_2\) 和 \(S_1+S_2+S_2\) 等等都是合法的。

所以我们有一个 DP：设 \(f_{i,j,0/1}\) 表示当前长度为 \(i\)、后面填 \(j\) 种数可以变成合法的、当前是否合法的方案数。则有转移：

• 如果当前是合法的，那么把当前的 \(j\) 种数再填一遍依然是合法的，且不会使下一步能填的数增加，故：\(f_{i+1,j,1}=\sum f_{i,j,1}\times j\)。
• 如果当前是合法的，那么把当前剩下的 \(m-j\) 种数填一遍就不合法了，但会使下一步能填的数增加，故：\(f_{i+1,j+1,0}=\sum f_{i,j,1}\times(m-j)\)。
• 如果当前不合法，按照状态，把 \(j\) 种数填一遍就会合法，且不会增加下一步能填的数，故：\(f_{i+1,j,1}=\sum f_{i,j,0}\times j\)。
• 如果当前不合法，把剩下的 \(m-j\) 种数填一遍依然不会合法，且不会增加下一步能填的数，故：\(f_{i+1,j,0}=\sum f_{i,j,0}\times(m-j)\)。

答案就是 \(\sum_{j=0}^nf_{n,j,1}\)。

#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
using namespace std;

char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
	int x=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}
template<typename T>
void write(T x,char sf='\n'){
	if(x<0)putchar('-'),x=~x+1;
	int top=0;
	do str[top++]=x%10,x/=10;while(x);
	while(top)putchar(str[--top]+48);
	if(sf^'#')putchar(sf);
}
using ll=long long;
constexpr int MAXN=3005,MOD=1e9+7;
int n,m,ans;
int f[MAXN][MAXN][2];
void add(int&x,int y){
	x=x+y>=MOD?x+y-MOD:x+y;
}

int main(){
	n=read(),m=read();
	f[1][1][0]=m;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=i;++j){
			add(f[i+1][j][0],(ll)f[i][j][0]*(m-j)%MOD);
			add(f[i+1][j][1],(ll)f[i][j][0]*j%MOD);
			add(f[i+1][j][1],(ll)f[i][j][1]*j%MOD);
			add(f[i+1][j+1][0],(ll)f[i][j][1]*(m-j)%MOD);
		}
	for(int i=1;i<=n;++i)add(ans,f[n][i][1]);
	write(ans);
	return fw,0;
}