Atcoder abc307

發表於 更新於 分類於 ， Disqus： 文章字數： 1.1k 所需閱讀時間 ≈ 4 分鐘
Ex(卷积,数学)

https://atcoder.jp/contests/abc307/tasks

Ex - Marquee

给定长度L的字符串S, 包含大小写字母, 在宽W的滚动显示器上，每次移动一个字母

因此有L+W-1种状态,例如S=ABC,W=5,点表示空

1
2
3
4
5
6
7
ABC..
BC...
C....
....A
...AB
..ABC
.ABC.

现在问题是 给定长度L字符串 T，问有多少个 状态和T匹配

T中有字符_可以匹配任意字符

l,w 3e5

5s

1024mb

我的思路

实际上滚动可以看成，S左侧W-1个点，右侧W-1个点

1
.....S.....

然后 用T去匹配

这匹配有点KMP的感觉，

但这里任意字符_ 似乎不是很好转移

一个想法是 KMP的树状版：AC自动机能有用吗？

但实际还是,KMP中 aba 的后缀最长匹配前缀的是a

而___的后缀最长匹配前缀是__

需要一个可以支持 通配符号的类似的 匹配算法

自匹配还算好，就是kmp的原理

dp[i]=i结尾后缀 相等的 最长前缀长度

dp[i] = dp[j] + 1, match(a[i],a[j+1]) and dp[i-1]最先递归向下到j

然而并不对

例如 样例1

1
2
ABC
..___

对于T来说 ..___ 的后缀(.___)match的最长前缀长度为4 (..__)

但是对于..ABC => .ABC. 转换 并不是只鉴定最后一位就可以的

也就是

1
2
3
4
5
 .ABC.
..ABC
..___
 ..__
 ..___

这个match关系没有传递性

但是是必要条件，因为S的子串如果match,则可以看成T的一个特例化，而如果 特例化对应match,则非特例化一定match

题解

也是先定义了两个字符串match的意义

这里也是先用拼接来转义旋转，不过是S...S, 但不影响，逻辑上和我的转换是等价的

同样也是 如果没有通配符号，就是个KMP问题

所以还是 如何处理通配符号

这里说ABC196F (我还没有补过), 0/1串，S和T，问最少需要翻转T多少个0/1让它变为S的子串

f(x,y) = xy+(1-x)(1-y) = [x==y], 来把 相等变成数学表达式的

从而计算 sum f(T_{i+k},P_k)

这里类似ABC196F的想法

创造 f(x,y) = 如果match0, 如果不match为正整数

那么 字符串匹配就是 sum f(X_i,Y_i) = 0

所以需要对于给定i,能计算 sum f(T_{i+k},P_k)

做char -> int 映射

_ = 0, 其它字符就直接ascii

那么有 $f(x,y) = (x-y)^2xy$ 可以满足我们的match需要

展开: $= x^3y-2x^2y^2+xy^3$, 这再去sum 就是显然的卷积！！！

然后显然的， 因为卷积是发生在mod 意义下的

而 3e5 * (max(f(x,y))) 如果 超过过mod ，可能会 false positive

而$\max((x-y)^2xy) = 1168650, x\in[0,53],y\in[0,53]$

肯定会超过 998244353

而$f(x,y)$ 还可以再改造

$f(x,y) = (x-y)^2 \mathrm{bool}(x) \mathrm{bool}(y) = x^2 \mathrm{bool}(x) \mathrm{bool}(y) - 2xy \mathrm{bool}(x) \mathrm{bool}(y) + y^2 \mathrm{bool}(x) \mathrm{bool}(y)$

这样范围就在 53^2内了，$3*10^5 * 53^2 = 842700000 < 998244353$

不会出现false positive了

需要准备的是 x^2, bool(y), x, y, bool(x), y^2

代码

https://atcoder.jp/contests/abc307/submissions/43393453

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
#include <bits/stdc++.h>
#include <atcoder/convolution>
#include <atcoder/modint>
using mint=atcoder::modint998244353;
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
ll read(){ll r;scanf("%lld",&r);return r;}
char tmp[300010];
int main(){
  int n=read();
  int w=read();

  vector<char> t(w-1,'.'); // ....S....
  scanf("%s",tmp);
  int sz = strlen(tmp);
  rep(i,0,sz) t.push_back(tmp[i]);
  rep(i,0,w-1) t.push_back('.');
  reverse(begin(t),end(t)); // 卷积翻转

  scanf("%s",tmp);
  sz=strlen(tmp);
  vector<char> p;
  rep(i,0,sz) p.push_back(tmp[i]);

  vector<int> num(max({'_','.','z','Z'})+1,0); // char => [0-53]
  num['_']=0;
  num['.']=1;
  rep(i,0,26)num['a'+i]=i+2;
  rep(i,0,26)num['A'+i]=i+2+26;

  vector<mint> t1(t.size()),t2(t.size()),tb(t.size()); // ^1,^2,bool
  vector<mint> p1(p.size()),p2(p.size()),pb(p.size()); // ^1,^2,bool
  rep(i,0,t.size()){
    int x=num[t[i]];
    t2[i]=x*(t1[i]=x*(tb[i] = bool(x)));
  }
  rep(i,0,p.size()){
    int x=num[p[i]];
    p2[i]=x*(p1[i]=x*(pb[i] = bool(x)));
  }
  // (x-y)^2 bool(x) bool(y)
  // x^2 bool(x) bool(y) - 2xy bool(x) bool(y) + bool(x) y^2 bool(y)
  auto f1=convolution(t2,pb);
  auto f2=convolution(t1,p1);
  auto f3=convolution(tb,p2);
  int ans=0;
  rep(i,w-1,(w-1)+(n+w-1)) ans += (f1[i]-2*f2[i]+f3[i]==0);
  printf("%d\n",ans);
}

总结

Ex

之前没有补 abc196f, 这个 转换成函数，从而变成卷积，倒过来看也很自然!!!, 学习了

参考

官方题解