[PA2021] Od deski do deski

看似简单，实则考察的是选手的 DP 基本功，如果像我一样只会观察性质就做不出来这题。

性质：合法的序列一定是由若干个子串按照顺序拼起来的，其中每个子串的开头和结尾是一样的。

然后的想法就是设 \(f_i\) 表示子串 \(i\) 能一次消掉的方案数，然后就会一直算重没法做。

这种感觉就像当年 csp，就是做计数 dp 内味。

从头开始，考虑更好地描述一个序列是否合法，有一个 dp：设 \(f_i\) 表示 \([1, i]\) 是否合法，值域为 \([0,1]\)，然后可以枚举最后一段转移。

有没有什么办法可以忽略原序列的信息就转移这个东西呢？有！直接设 \(j\) 表示有 \(j\) 种数填进去就能使得 \(f_i\) 合法。这样我们就不用关心原序列的信息了。

考虑在此基础上可以设计原题的状态：\(f_{i,j,0/1}\) 表示长度为 \(i\) 的序列，有 \(j\) 种数填入后就变合法，当前是否合法的方案数，转移是平凡的。

const int N = 3010;
int n, m;
int f[N][N][2];

const int P = 1e9 + 7;
void add(int &x, int y) {
  (x += y) >= P ? x -= P : 0;
}

int main() {
  read(n, m);
  f[0][0][1] = 1;
  for(int i = 1; i <= n; ++i) {
    for(int j = 0; j < i; ++j) {
      add(f[i][j + 1][0], 1ll * f[i - 1][j][1] * (m - j) % P);
      add(f[i][j][1], 1ll * f[i - 1][j][1] * j % P);
      add(f[i][j][1], 1ll * f[i - 1][j][0] * j % P);
      add(f[i][j][0], 1ll * f[i - 1][j][0] * (m - j) % P);
    }
  }
  int ans = 0;
  for(int i = 0; i <= n; ++i)
    add(ans, f[n][i][1]);
  printf("%d\n",ans);
}