BZOJ 1566 「NOI2009」管道取珠

发表于 | 分类于

Description

有两个长度分别为\(n,m\)的珠子序列\(S,T\)，每种珠子可能是黑色或者白色，同色的珠子视为本质相同。

我们进行\(n + m\)次操作，每次从\(S,T\)中的一个的头部取出一个珠子，放到我们结果序列的尾部，这样能形成一个新的序列。定义两种方案不同，当且仅当存在一步使得这一步两种方案一个从\(S\)取一个从\(T\)取。那么我们假设最后可能的结果序列有\(k\)种，我们把他们用\(1\ldots k\)编号，假设\(a_k\)为编号为\(k\)的序列的操作方案数量，求： \[ \sum_{i = 1}^k a_i^2 \] \(n,m\leq 500\)。

Solution

那个平方是不是很不好处理啊……

那么\(a_i\)一定可以表示为若干个\(1\)相加，每个\(1\)都代表了一种可以形成序列\(i\)的操作方案，平方之后这些\(1\)就会两两配对（参考二项式定理？）。

那么问题就转化成了求有多少对（可以相同也可以不相同的）操作序列可以生成同样的结果序列。这个DP一下就好力，，，

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
25
26
27
28
29
30
31
32
33
#include <cstdio>
#include <cstring>
#include <cstdlib>
const int ha = 1024523;
int d[2][505][505];
char S[505], T[505];
int main() {
  int n, m; scanf("%d%d%s%s", &n, &m, S + 1, T + 1);
  d[0][0][0] = 1;
  for(int i = 1; i <= n + m; i ++) {
    int now = i & 1;
    int pre = now ^ 1;
    memset(d[now], 0, sizeof(d[now]));
    for(int j = 0; j <= i && j <= n; j ++) {
      if(i - j > m) continue;
      for(int k = 0; k <= i && k <= n; k ++) {
        if(i - k > m) continue;
        int &ans = d[now][j][k];
        bool A0 = j > 0, B0 = k > 0;
        bool A1 = j < i, B1 = k < i;
        if(A0 && B0 && S[j] == S[k]) ans = (ans + d[pre][j - 1][k - 1]) % ha;
        if(A1 && B1 && T[i - j] == T[i - k]) ans = (ans + d[pre][j][k]) % ha;
        if(A0 && B1 && S[j] == T[i - k]) ans = (ans + d[pre][j - 1][k]) % ha;
        if(A1 && B0 && T[i - j] == S[k]) ans = (ans + d[pre][j][k - 1]) % ha;
#ifdef LOCAL
        printf("d[%d][%d][%d] : %d\n", i, j, k, ans);
#endif
      }
    }
  }
  printf("%d\n", d[(n + m) & 1][n][n]);
  return 0;
}