F - Common Prefixes
题目
https://atcoder.jp/contests/abc213/tasks/abc213_f
给长n字符串S
求其每个位置开始的后缀字符串, 和所有其它后缀字符串的 公共前缀和
范围
n 1e6
3s
1024mb
题解
官方
知识点 后缀数组 SA
那么对于 后缀i
它在SA中的位置是 rank[i]
有高度数组表示 rank[i] 和 rank[i-1]的最长公共前缀
那么就是 min(height[0..i]]) + min(height[1..i]) +… + min(height[i..i]) + (n-i) + min(height[i+1..i+1]) + .. + min(height[i+1..n])
直接枚举依然不行
考虑 可以单调栈维护计算其中一半
代码
https://atcoder.jp/contests/abc213/submissions/33587517
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back
#define mp make_pair
ll read(){ll r;scanf("%lld",&r);return r;}
const int N = 1000000;
char s[N+10];
int rk[N+10];
int rk0[N+10];
int h[N+10];
int sa[N+10];
ll pre[N+10];
ll suf[N+10];
int main(){
int n = read();
scanf("%s", s);
iota(sa,sa+n,0);
sort(sa,sa+n,[=](int i,int j){return s[i] < s[j];});
rk[sa[0]] = 0;
rep(i,1,n) rk[sa[i]] = rk[sa[i-1]] + (s[sa[i]] != s[sa[i-1]]);
rep(pwr,0,22){
int w = 1<<pwr;
if(w > n) break;
rep(i,0,n) rk0[i] = rk[i];
auto f = [=](int i){return i < n?rk0[i]:-1;};
sort(sa,sa+n,[=](int i,int j){ return mp(f(i),f(i+w)) < mp(f(j),f(j+w));});
rk[sa[0]] = 0;
rep(i,1,n) rk[sa[i]] = rk[sa[i-1]] + (mp(f(sa[i]),f(sa[i]+w)) != mp(f(sa[i-1]),f(sa[i-1]+w)));
}
int hei = 0;
rep(i,0,n){
if(!rk[i]) continue;
if(hei) hei--;
while(s[i + hei] == s[sa[rk[i]-1] + hei]) hei++;
h[rk[i]] = hei;
}
{
vector<int> stk = {};
rep(i,1,n) {
while(stk.size() && h[i] < h[stk.back()]) stk.pop_back();
int last = stk.size() ? stk.back() : 0;
pre[i] = pre[last] + h[i] * (i - last);
stk.push_back(i);
}
}
{
vector<int> stk = {};
per(i,1,n) {
while(stk.size() && h[i] < h[stk.back()]) stk.pop_back();
int last = stk.size() ? stk.back() : n;
suf[i] = suf[last] + h[i] * (last - i);
stk.push_back(i);
}
}
rep(i,0,n) printf("%lld\n",(n-i) + pre[rk[i]] + suf[rk[i]+1]);
return 0;
}
|
G - Connectivity 2
https://atcoder.jp/contests/abc213/tasks/abc213_g
无向图
n 点, m 边
考虑移除任意条边得到新图G, 有$2^m$种新图G
对于每个点$u\in[2,n]$, 计算在所有新图中, $u$和$1$属于同一连通块的个数
mod 9098244353
范围
n 17
无重边,无自环
3s
1024mb
题解
显然, $n \le 17$ 是个bitmask的题
$2^{17} = 131072$
定义mask为点1所在的联通块点集, 那么其实状态只有$2^{16}$了
cnt[mask] = 边(两个端点都属于mask)的数量
对于剩下m - cnt[mask]条边
- 如果端点均不在mask中, 则是否选边对mask没有影响, 那么是2幂次倍数
- 如果端点一个在mask中,一个不在mask中, 则不可选, 否则mask会变化
导出子图(induced subgraph)是指，由该图顶点的一个子集和该图中两端均在该子集的所有边的集合组成的图。
定义 $dp[S] =$连通块为点集$S$时, 选的边端点均属于S的选边方案数, 不考虑$S$以外的边的情况
$dp[S] = 2^{cnt(S)} - \sum_{1\in T, T\subset S} dp[T] \cdot 2^{cnt(S-T)}$
解释这个$dp$: 所有方案($2^{cnt(S)}$)($S$的每条边可选可不选) - 非所有点连通的方案(即是一个包含1的非所有点连通块,以及不包含1的连通块内的点的剩余边随便连)
这里所有计算的$S$都包含点1
那么$ans(u) = \sum_{1\in S,u\in S} dp[S] \cdot 2^{cnt(全集 - S)}$
$cnt[mask]$ 暴力 预计算 $O(m 2^n)$
计算dp, 需要真子集遍历$O(3^{n-1})$
计算答案 $O(n 2^n)$
代码
https://atcoder.jp/contests/abc213/submissions/33590273
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 998244353
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
ll read(){ll r;scanf("%lld",&r);return r;}
const int N = 1<<17;
int f[N+10];
int c[N+10];
ll p2[150]={1};
ll ans[20];
int main(){
rep(i,1,140) p2[i]=2*p2[i-1]%MOD;
int n = read();
int m = read();
rep(i,0,m){
int u = read() - 1;
int v = read() - 1;
rep(mask,0,p2[n]) if((mask & p2[u]) && (mask & p2[v])) c[mask]++;
}
rep(S0,0,p2[n-1]){
int S = 2*S0+1;
f[S] = p2[c[S]];
for(int T0=S0&(S0-1);S0;T0=(T0-1)&S0){
int T = 2*T0 + 1;
(f[S] -= f[T] * p2[c[S-T]] % MOD) %= MOD;
if(!T0)break;
}
rep(i,1,n) if(S & p2[i]) (ans[i] += f[S]*p2[c[p2[n]-1-S]] % MOD) %= MOD;
}
rep(i,1,n) printf("%lld\n", (ans[i]+MOD) % MOD);
}
|
H/Ex - Stroll
https://atcoder.jp/contests/abc213/tasks/abc213_h
N个点
M 个点对, 连接ui,vi, p[i][d]条路 长度d的路, (d [1,T])
找从点1开始,点1结束,长度等于T的路径方案数
范围
n 10
m min(10,n(n-1)/2)
t 4e4
p[1..m][1..T] \in [0,998244353]
题解
我的思路
一眼递推
f[u][d] = 到u步数为T的方案数
那么每次找未贡献的最小的d
f[v][d+step] += p[边[u <-> v]][step] * f[u][d]
但这样$NT$个状态, 每个状态会更新$MT$个点
看起来有$O(MNT^2)$
官方
dp[u][i]= 1 出发, 长度i, 走到u 方案数
考虑最后一次转移 从v到u, 走t步
$dp[u][i] = \sum_{(u,v)\in E} \sum_{t=1}^i dp[v][i-t] * p[e_{u,v}][t]$
直接NTT依然不行
因为它们相互依赖
于是来到了分治NTT
cdq 分治 + NTT/fft 框架
1
2
3
4
| solve(l..r):
solve(l..mid)
solve(mid+1..r)
|
代码
https://atcoder.jp/contests/abc213/submissions/me
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
| #include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using mint=atcoder::modint998244353;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back
ll read(){ll r;scanf("%lld",&r);return r;}
ll n;
ll p[20][40010];
mint dp[20][40010];
vector<pair<int,int>> e[20];
void solve(ll l,ll r) {
if(l==r) return;
ll mid=(l+r)/2;
solve(l, mid);
rep(u,1,n+1) for(auto [v,eid]:e[u]) {
vector <mint> A = {};
vector <mint> B = {0};
rep(i,l,mid+1) A.pb(dp[u][i]);
rep(i,1,(r-l+1)+1) B.pb(p[eid][i]);
auto C = atcoder::convolution(A,B);
rep(i,mid+1,r+1) dp[v][i]+=C[i-l].val();
}
solve(mid+1,r);
}
int main() {
n = read();
ll m = read();
ll t = read();
rep(i,0,m) {
ll u = read();
ll v = read();
e[u].pb({v,i});
e[v].pb({u,i});
rep(j,1,t+1) p[i][j] = read();
}
dp[1][0] = 1;
solve(0,t);
printf("%d\n",dp[1][t].val());
return 0;
}
|
总结
F
知识点 后缀数组 与高度数组
G
感觉有点集合论转移的思路,没有类似的练习
然后就是如何做分类和贡献统计, 这里是按照和1连通的作为一个分类的依据
分别记录内部方案数, 和 外部方案倍数, 外部倍数相对好算, 而内部方案数 需要dp推导
所有子集遍历的复杂度是$3^n$ 不是$4^n$
H
除了dp还可以数学直接表示到目标点, 从而引申出求和 有卷积
这里新知识点是分治NTT
atcoder 提供 atcoder::modint998244353, 以及卷积 atcoder::convolution
关于Ubuntu 使用, 最简单就是, 克隆下来做个软链接
1
2
3
| git clone git@github.com:atcoder/ac-library.git
cd /usr/local/include/
sudo ln -s 克隆路径/atcoder
|
参考
官方题解
https://atcoder.jp/contests/abc213/editorial/2410