CF100958I Substring Pairs DP

发表于 更新于 分类于 阅读次数：

[Makoto Soejima Contest 1, Japanese Grand Prix, by rng_58][CF100958I] Substring Pairs 上面的来源有长长的一串，是因为在陈老师WC课件里见过这个题，来源很迷，全粘贴上了… 考虑一下给定$T$怎么求有多少个$S$，令$f_i$表示$i$处，$[i-m+1,i]$是$T$第一次出现的方案。$f_i=A^{i-m}-\sum_{j < i} f_j W_{i,j} $，意思是枚举上一次出现的位置。$W$的值取决于两个串是否相交，如果相交要求交的部分是Border。 可以看出，这个DP只和$T$的Border集合有关。那么考虑枚举集合并DP即可。这里有一个貌似好几道题都用到的结论：$\sum_{i \leq 50} border \ cnt_i \leq 30000$。那么暴搜出所有Border就行了。 爆搜的方法也很简单：维护一个当前的Border，扩展串的长度，使得当前Border是新的串的Border，递归即可。当前串的新的串的Border的条件是，如果当前串长度大于新串的一半，那么需要判断重复的部分是不是Border。另外由于不能重复，需要去重。考虑重复的条件：考虑扩展后长度小于二分之一，中间随便放，那么可能存在一种放法，使得中间位置也有Border，显然已经被算过，所以减去之前的答案和就行了。 为什么CF非>=紫名的用户不能看Gym别人代码啊啊啊啊想找个程序对拍都找不到

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>

const int N = 205, P = 1e9 + 7;

int n, m, A;
long long powA[N];
long long ans;
std::vector<int> border;

inline long long calc(int x, int y, __int128 S) {
  if (y < x - m + 1) {
    return powA[x - m - y];
  }
  return (S >> (y - x + m)) & 1;
}

inline long long dp(__int128 S) {
  if (!(((__int128)1 << m) & S))
    return 0;
  if (S >> (m + 1))
    return 0;
  long long ret = 0;
  std::vector<long long> f(N);
  for (int i = m; i <= n; ++i) {
    f[i] = powA[i - m];
    for (int j = m; j < i; ++j)
      f[i] = (f[i] + P - f[j] * calc(i, j, S) % P);
    f[i] %= P;
    ret = (ret + f[i] * powA[n - i]) % P;
  }
  return ret % P;
}

std::vector<int> dfs(__int128 S, int ways) {
  ans = (ans + dp(S) * ways) % P;
  int last = border.back();
  std::vector<int> ret(N);
  ret[last] = (ret[last] + ways) % P;
  for (int x = last + 1; x <= m; ++x) {
    border.push_back(x);
    int tmp = ways;
    for (int i = 0; i + 1 < border.size(); ++i) {
      int v = border[i];
      if (v + v > x && !(S & ((__int128)1 << (v + v - x))))
        goto next;
    }
    if (last + last < x)
      tmp = tmp * powA[x - last - last] % P;
    tmp = (tmp - ret[x] + P) % P;
    if (tmp) {
      std::vector<int> vec = dfs(S  ((__int128)1 << x), tmp);
      for (int i = 0; i <= m; ++i)
        ret[i] = (ret[i] + vec[i]) % P;
    }
    next:
    border.pop_back();
  }
  return ret;
}

int main() {
  std::cin >> n >> m >> A;
  powA[0] = 1;
  for (int i = 1; i < N; ++i)
    powA[i] = powA[i - 1] * A % P;
  border.push_back(0);
  dfs(0, 1);
  std::cout << ans << std::endl;
  return 0;
}