【BZOJ 3881】[COCI2015] Divljak

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3881
神犇题解:http://trinkle.is-programmer.com/2015/6/30/bzoj-3881.100056.html

解题报告

考虑把Alice的串建成AC自动机
那么每一次用Bob的串去匹配就是Fail树上一些树链的并
这个用BIT+虚树无脑维护一下就可以了

Code

#include<bits/stdc++.h>
#define LL long long
#define lowbit(x) ((x)&-(x))
using namespace std;

const int N = 2000009;
const int LOG = 26;
const int SGZ = 26;

int in[N];

inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

class Ac_Automaton{
int root, cnt, ch[N][SGZ], fail[N], pos[N], dep[N];
int head[N], to[N], nxt[N], ot[N], fa[N][LOG];
class FenwickTree{
int mx, sum[N];
public:
	inline void init(int nn) {
		mx = nn;
	}
	inline void modify(int p, int d) {
		for (int i = p; i <= mx; i += lowbit(i)) {
			sum[i] += d;
		}
	}
	inline int query(int l, int r) {
		int ret = 0;
		for (int i = l - 1; i > 0; i -= lowbit(i)) {
			ret -= sum[i];
		}
		for (int i = r; i; i -= lowbit(i)) {
			ret += sum[i];
		}
		return ret;
	}
private:
}bit;
public:
	inline void insert(char *s, int nn, int id) {
		int w = root;
		for (int i = 1; i <= nn; i++) {
			int cc = s[i] - 'a';
			if (!ch[w][cc]) {
				ch[w][cc] = ++cnt;
			}
			w = ch[w][cc];
		} 
		pos[id] = w;
	}
	inline void build() {
		static queue<int> que;
		for (int i = 0; i < SGZ; i++) {
			if (ch[root][i]) {
				que.push(ch[root][i]);
			}
		}
		for (; !que.empty(); que.pop()) {
			int w = que.front();
			AddEdge(fail[w], w);
			for (int i = 0; i < SGZ; i++) {
				if (!ch[w][i]) {
					ch[w][i] = ch[fail[w]][i];
				} else {
					que.push(ch[w][i]);
					fail[ch[w][i]] = ch[fail[w]][i];
				}
			}
		}
		DFS(0, 0);
		for (int j = 1; j < LOG; j++) {
			for (int i = 0; i <= cnt; i++) {
				fa[i][j] = fa[fa[i][j - 1]][j - 1];
			}
		}
		bit.init(cnt + 1);
	} 
	inline void match(char *s, int nn) {
		static vector<int> vt[N];
		static int que[N], stk[N], vis[N]; 
		int qtot = 0, stot = 0, vtot = 0;
		que[++qtot] = root;
		for (int i = 1, w = root; i <= nn; i++) {
			w = ch[w][s[i] - 'a'];
			que[++qtot] = w;
		}
		sort(que + 1, que + 1 + qtot);
		qtot = unique(que + 1, que + 1 + qtot) - que - 1;
		sort(que + 1, que + 1 + qtot, cmp);
		for (int i = 1; i <= qtot; i++) {
			if (stot) {
				int lca = LCA(que[i], stk[stot]);
				for (; stot && dep[stk[stot]] > dep[lca]; --stot) {
					if (stot > 1 && dep[stk[stot - 1]] >= dep[lca]) {
						vt[stk[stot - 1]].push_back(stk[stot]);
					} else {
						vt[lca].push_back(stk[stot]);
					}
				}
				if (stot && stk[stot] != lca) {
					stk[++stot] = lca;
					vis[++vtot] = lca;
				}
			} 
			stk[++stot] = que[i];
			vis[++vtot] = que[i];
		}
		for (; stot > 1; --stot) {
			vt[stk[stot - 1]].push_back(stk[stot]);
		}
		update(root, vt);
		for (int i = 1; i <= vtot; i++) {
			vt[vis[i]].clear();
		}
	}
	inline int query(int id) {
		return bit.query(in[pos[id]], ot[pos[id]]);
	}
private:
	inline void update(int w, vector<int> *vt) {
		for (int i = 0; i < (int)vt[w].size(); i++) {
			bit.modify(in[w], -1);
			bit.modify(in[vt[w][i]], 1);
			update(vt[w][i], vt);
		}
	}
	inline int LCA(int a, int b) {
		if (dep[a] < dep[b]) {
			swap(a, b);
		}
		for (int j = SGZ - 1; ~j; j--) {
			if (dep[fa[a][j]] >= dep[b]) {
				a = fa[a][j];
			}
		}
		if (a == b) {
			return a;
		}
		for (int j = SGZ - 1; ~j; j--) {
			if (fa[a][j] != fa[b][j]) {
				a = fa[a][j];
				b = fa[b][j];
			}
		}
		return fa[a][0];
	} 
	static bool cmp(int a, int b) {
		return in[a] < in[b];
	}
	inline void DFS(int w, int f) {
		static int tt = 0;
		in[w] = ++tt;
		dep[w] = dep[fa[w][0] = f] + 1;
		for (int i = head[w]; i; i = nxt[i]) {
			DFS(to[i], w);
		}
		ot[w] = tt;
	}
	inline void AddEdge(int u, int v) {
		static int E = 1;
		to[++E] = v; nxt[E] = head[u]; head[u] = E;
	}
}ac;

int main() {
	static char ss[N];
	int n = read();
	for (int i = 1; i <= n; i++) {
		scanf("%s", ss + 1);
		int len = strlen(ss + 1);
		ac.insert(ss, len, i);
	}
	ac.build();
	int m = read();
	for (int i = 1; i <= m; i++) {
		if (read() == 1) {
			scanf("%s", ss + 1);
			int len = strlen(ss + 1);
			ac.match(ss, len);
		} else {
			printf("%d\n", ac.query(read()));
		}
	}
	return 0;
}

【BZOJ 3940】[Usaco2015 Feb] Censoring

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3940

解题报告

用栈和AC自动机来模拟即可

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int SGZ = 26;

char ctn[N], wrd[N]; 

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

class AC_Automaton{
int Root, cnt, ch[N][SGZ], apt[N], dep[N], fail[N];
queue<int> que;
public:
	inline void insert(char *s, int len) {
		int w = Root;
		for (int i = 1; i <= len; i++) {
			int  cc = s[i] - 'a';
			if (!ch[w][cc]) {
				ch[w][cc] = ++cnt;
				dep[cnt] = dep[w] + 1;
			}
			w = ch[w][cc];
		}
		apt[w] = len;
	}
	inline void build() {
		for (int i = 0; i < SGZ; i++) {
			if (ch[Root][i]) {
				que.push(ch[Root][i]);
			}
		}
		for (; !que.empty(); que.pop()) {
			int w = que.front();
			for (int i = 0; i < SGZ; i++) {
				if (ch[w][i]) {
					fail[ch[w][i]] = ch[fail[w]][i];
					apt[ch[w][i]] = max(apt[ch[w][i]], apt[fail[ch[w][i]]]);
					que.push(ch[w][i]);
				} else {
					ch[w][i] = ch[fail[w]][i];
				}
			}
		}
	}
	inline int root() {
		return Root;
	}
	inline int move(int &w, int cc) {
		w = ch[w][cc];
		return apt[w];
	}
}aca;

int main() {
	scanf("%s", ctn + 1);
	int n = read(), m = strlen(ctn + 1);
	for (int i = 1; i <= n; i++) {
		scanf("%s", wrd + 1);
		aca.insert(wrd, strlen(wrd + 1));
	}
	aca.build();
	vector<int> ans, pos;
	for (int i = 1; i <= m; i++) {
		int w = pos.empty()? aca.root(): *--pos.end();
		int len = aca.move(w, ctn[i] - 'a');
		ans.push_back(ctn[i]);
		pos.push_back(w);
		for (int j = 1; j <= len; j++) {
			ans.pop_back();
			pos.pop_back();
		}
	}
	for (int i = 0; i < (int)ans.size(); i++) {
		putchar(char(ans[i]));
	}
	return 0;
}

【BZOJ 4566】[HAOI2016] 找相同字符

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4566

解题报告

我们可以拿一个串建SAM,把另一个串扔到SAM中匹配一遍
也可以直接把两个串拼一起,然后建SAM,最后遍历一下就好

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 800009;
const int SGZ = 27;
 
int n, m;
char s[N];
 
class Suffix_Automaton{
int cnt, tail, ch[N][SGZ], fail[N], sz[N][2], len[N], head[N], nxt[N], to[N];
public:
    inline void init() {
		cnt = tail = 1;
        for (int i = 1; i <= n; i++) {
            append(s[i] - 'a', 0);
        }
        append(SGZ - 1, -1);
        for (int i = n + 2; i <= n + m + 1; i++) {
            append(s[i] - 'a', 1);
        }
        for (int i = 1; i <= cnt; i++) {
            AddEdge(fail[i], i);
        }
        DFS(0, 0);
    }
    inline LL query() {
        LL ret = 0;
        for (int i = 1; i <= cnt; i++) {
            ret += (LL)(len[i] - len[fail[i]]) * sz[i][0] * sz[i][1];
        }
        return ret;
    } 
private:
    inline void DFS(int w, int f) {
        for (int i = head[w]; i; i = nxt[i]) {
            if (to[i] != f) {
                DFS(to[i], w);
                sz[w][0] += sz[to[i]][0];
                sz[w][1] += sz[to[i]][1];
            }
        }
    }
    inline void AddEdge(int u, int v) {
        static int E = 1;
        to[++E] = v; nxt[E] = head[u]; head[u] = E;
    }
    inline void append(char cc, int t) {
        int w = tail, cur = ++cnt;
        if (t != -1) {
            sz[cur][t] += 1;
        }
        len[cur] = len[tail] + 1;
        for (tail = cur; w && !ch[w][cc]; ch[w][cc] = cur, w = fail[w]);
        if (w) {
            if (len[ch[w][cc]] == len[w] + 1) {
                fail[cur] = ch[w][cc];
            } else {
                int nt = ++cnt, pt = ch[w][cc]; 
                memcpy(ch[nt], ch[pt], sizeof(ch[nt]));
                len[nt] = len[w] + 1;
                fail[nt] = fail[pt];
                fail[cur] = fail[pt] = nt;
                for (; w && ch[w][cc] == pt; ch[w][cc] = nt, w = fail[w]);
            }
        } else {
			fail[cur] = 1;
		}
    } 
}sam;
 
int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    s[n + 1] = 'z' + 1;
    scanf("%s", s + n + 2);
    m = strlen(s + n + 2);
    sam.init();
    printf("%lld\n", sam.query());
    return 0;
}

【BZOJ 4278】[ONTAK2015] Tasowanie

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4278

解题报告

考虑归并排序
唯一麻烦的地方就是两个字符相同时选哪个
我们可以比较后缀的字典序来解决这个问题
具体实现上,我们可以使用SA

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 800009;
const int SGZ = 1001;

int n, m, s[N];
class Suffix_Array{
int *rk, *tmp, sa[N], bot[N], arr1[N], arr2[N], que[N];
public:
	inline void build(int *s, int nn) {
		rk = arr1; tmp = arr2; int sgz = SGZ;
		for (int i = 1; i <= nn; i++) bot[s[i]]++;
		for (int i = 1; i <= sgz; i++) bot[i] += bot[i - 1];
		for (int i = 1; i <= nn; i++) que[bot[s[i]]--] = i;
		rk[que[1]] = sgz = 1; 
		for (int i = 2; i <= nn; i++) rk[que[i]] = (sgz += s[que[i]] != s[que[i - 1]]);
		for (int l = 1; l < nn && sgz < nn; l <<= 1) {
			int tt = 0;
			for (int i = nn - l + 1; i <= nn; i++) tmp[++tt] = i;
			for (int i = 1; i <= nn; i++) if (que[i] > l) tmp[++tt] = que[i] - l;
			for (int i = 0; i <= sgz; i++) bot[i] = 0;
			for (int i = 1; i <= nn; i++) bot[rk[i]]++;
			for (int i = 1; i <= sgz; i++) bot[i] += bot[i - 1];
			for (int i = nn; i; i--) que[bot[rk[tmp[i]]]--] = tmp[i];
			swap(rk, tmp); rk[que[1]] = sgz = 1;
			for (int i = 2; i <= nn; i++) {
				rk[que[i]] = (sgz += tmp[que[i]] != tmp[que[i - 1]] || tmp[que[i] + l] != tmp[que[i - 1] + l]);
			}
		}
	}
	inline int rank(int p) {
		return rk[p];		
	}
}sa;

inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

int main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		s[i] = read();
	}
	s[n + 1] = 1001;
	m = read();
	for (int i = 1; i <= m; i++) {
		s[i + n + 1] = read();
	}
	sa.build(s, n + m + 1);
	for (int i = 1, j = 1, k = 1; k <= n + m; k++) {
		if (i <= n && j <= m) {
			if (s[i] < s[j + n + 1] || (s[i] == s[j + n + 1] && sa.rank(i) < sa.rank(j + n + 1))) {
				printf("%d ", s[i++]);
			} else {
				printf("%d ", s[n + 1 + j++]);
			}
		} else if (i <= n) {
			printf("%d ", s[i++]);
		} else {
			printf("%d ", s[n + 1 + j++]);
		}
	}
	return 0;
}

【HDU 5716】带可选字符的多字符串匹配

相关链接

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5716
神犇题解:http://www.cnblogs.com/clrs97/p/5985648.html

解题报告

这货$KMP$是不可做的,于是考虑用$bitset$来优化暴力
定义$v[i][j]$为文本串第$i$位是否能匹配模式串第$j$位
定义$f[i][j]$为第$i$种字符能否匹配模式串第$j$位
那么$v[i][j] = v[i – 1][j – 1] \ and \ f[s[i]][j]$
然后数组第二维用$bitset$优化,时间复杂度:$O(\frac{nm}{64})$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 2000009;
const int M = 600;
const int SGZ = 100;

char s[N], sgz[SGZ];
bitset<M> v, f[SGZ];

inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

inline int id(char c) {
	if ('0' <= c && c <= '9') {
		return c - '0' + 1;
	} else if ('a' <= c && c <= 'z') {
		return c - 'a' + 11;
	} else if ('A' <= c && c <= 'Z'){
		return c - 'A' + 37;
	} else {
		return 0;
	}
}

int main() {
	while (gets(s + 1)) {
		int n = strlen(s + 1), m = read();
		v.reset();
		for (int i = 0; i < SGZ; i++) {
			f[i].reset();
		}
		for (int i = 1; i <= m; i++) {
			int SGZ = read();
			scanf("%s", sgz + 1);
			for (int j = 1; j <= SGZ; j++) {
				f[id(sgz[j])][i] = 1;
			}
		}
		bool CantMatch = 1;
		for (int i = 1; i <= n; i++) {
			v = (v << 1) & f[id(s[i])];
			v[1] = f[id(s[i])][1];
			if (v[m]) {
				printf("%d\n", i - m + 1);
				CantMatch = 0;
			}
		}
		if (CantMatch) {
			puts("NULL");
		}
		getchar();
	}
	return 0;
}

—————————— UPD 2017.7.3 ———————————
这题的简单拓展:http://www.lydsy.com/JudgeOnline/problem.php?id=4924

【Codeforces 817E】Choosing The Commander

相关链接

题目传送门:http://codeforces.com/contest/817/problem/E

解题报告

考虑异或之后小于的话
把士兵插入到Trie树里面,然后走一条链即可
时间复杂度:$O(n \log 10^8)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009 * 32;

inline int read() {
	char c = getchar();
	int ret = 0, f = 1;
	while (c < '0' || c > '9') {
		f = c == '-'? -1: 1;
		c = getchar();
	}
	while ('0' <= c && c <= '9') {
		ret = ret * 10 + c - '0';
		c = getchar();
	}
	return ret * f;
}

class Trie{
int root, cnt;
struct Node{
	int sum, ch[2];
}p[N];
public:
	inline void modify(int v, int d) {
		modify(root, 30, v, d);
	}
	inline int query(int buf, int lim) {
		return query(root, 30, buf, lim);
	}
private:
	inline void modify(int &w, int t, int v, int d) {
		w = w? w: ++cnt;
		p[w].sum += d;
		if (t >= 0) {
			modify(p[w].ch[(v >> t) & 1], t - 1, v, d);
		}
	}
	inline int query(int w, int t, int buf, int lim) {
		if (!w || t == -1) {
			return 0;
		} else {
			int ret = 0, t2 = (buf >> t) & 1, t1 = (lim >> t) & 1;
			if (t1) {
				ret += p[p[w].ch[t2]].sum;
				ret += query(p[w].ch[t2 ^ 1], t - 1, buf, lim);
			} else {
				ret += query(p[w].ch[t2], t - 1, buf, lim);
			}
			return ret;
		}
	}
}trie;

int main() {
	int n = read();
	for (int i = 1; i <= n; i++) {
		int ty = read();
		if (ty == 1) {
			trie.modify(read(), 1);
		} else if (ty == 2) {
			trie.modify(read(), -1);
		} else {
			int p = read(), l = read();
			printf("%d\n", trie.query(p, l));
		}
	}
	return 0;
}

【BZOJ 4212】神牛的养成计划

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4212
神犇题解:http://www.cnblogs.com/yousiki/p/6550484.html

解题报告

这题如果没有强制在线,那么我们可以用$Trie + bitset$在$O(\frac{2000000n}{64})$的时间复杂度过
如果强制在线并且$s1,s2$等长,那么我们可以在$O(2000000 \log 2000000)$的时间复杂度过

现在解决原问题,先考虑一个暴力:
先把前缀能匹配上的串找出来,然后我们在其中找出后缀能匹配的串
考虑一下后缀数组:按字典序排序后,前缀能匹配上的一定是一个区间
于是我们可以先建一个正串的$Trie$,用来找出前缀合法的字符串区间
然后我们将反串建成一个持久化$Trie$,每一次用前缀合法的区间再去查后缀即可

另外还有一点$Trick$就是字符串排序:我们可以先将正串建成$Trie$,然后贪心$DFS$
这样排序的复杂度就可以是线性的,总的时间复杂度也就是线性的了

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 2000009;
const int M = 2009;
const int SGZ = 26;

int n,m,tot,beg[M],sz[M],ord[M];
char s1[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

class Trie{
	int cnt,ch[N][26],mn[N],mx[N];
	vector<int> id[N];
	public:
		inline void insert(char *s, int len, int ID) {
			int w = 0;
			for (int i=0;i<len;i++) {
				int c = s[i] - 'a';
				if (!ch[w]) ch[w] = ++cnt;
				w = ch[w];
			} 
			id[w].push_back(ID);
		}
		inline void sort(int w, int *arr, int &cur) {
			for (int i=0;i<id[w].size();i++) {
				arr[++cur] = id[w][i];
			}
			for (int i=0;i<SGZ;i++) {
				if (ch[w][i]) {
					sort(ch[w][i], arr, cur);
				}
			}
		}
		inline void mark(int val, char *s, int len) {
			int w = 0;
			for (int i=0;i<len;i++) {
				int c = s[i] - 'a';
				w = ch[w];
				if (!mn[w] || mn[w] > val) mn[w] = val;
				if (!mx[w] || mx[w] < val) mx[w] = val;
			}
		}
		inline void query(char *s, int len, int &l, int &r) {
			int w = 0;
			for (int i=0;i<len;i++) {
				int c = s[i] - 'a';
				if (!ch[w]) {
					l = 1; r = 0;
					return;
				} else {
					w = ch[w];
				}
			}
			l = mn[w]; 
			r = mx[w]; 
		}
	private:
}trie; 

class Persistent_Trie{
	int cnt,root[M],sum[N],ch[N][26];
	public:
		inline void insert(int p, int w, char *s, int len) {
			Insert(root[p], root[w], s, len); 
		}
		inline int query(int l, int r, char *s, int len) {
			if (l > r) return 0;
			int ret = 0, w = root[r]; 
			for (int i=0;i<len;i++) {
				w = ch[w][s[i]-'a']; 
			}
			ret += sum[w];
			w = root[l-1];
			for (int i=0;i<len;i++) {
				w = ch[w][s[i]-'a'];
			}
			ret -= sum[w];
			return ret;
		}
	private:
		void Insert(int p, int &w, char *s, int len) {
			w = ++cnt;
			sum[w] = sum[p] + 1;
			memcpy(ch[w], ch[p], sizeof(ch[w]));
			if (len <= 0) return;
			int c = s[len-1] - 'a'; 
			Insert(ch[p], ch[w], s, len - 1);
		}
}PTE; 

int main() {
	n = read();
	for (int i=1,last=0;i<=n;i++) {
		beg[i] = last;
		scanf("%s", s1+last);
		sz[i] = strlen(s1+last);
		trie.insert(s1+last, sz[i], i);
		last += sz[i];
	}
	tot = 0;
	trie.sort(0, ord, tot);
	for (int i=1;i<=n;i++) {
		trie.mark(i, s1+beg[ord[i]], sz[ord[i]]);
		PTE.insert(i-1, i, s1+beg[ord[i]], sz[ord[i]]);
	}
	m = read(); 
	for (int tt=1,last=0,l,r;tt<=m;tt++) {
		scanf("%s",s1);
		int len = strlen(s1);
		for (int i=0;i<len;i++) {
			s1[i] = (s1[i] - 'a' + last) % SGZ + 'a';
		} 
		trie.query(s1, len, l, r);
		scanf("%s",s1);
		len = strlen(s1);
		for (int i=0,j=len-1;i<j;i++,j--) {
			swap(s1[i], s1[j]);
		}
		for (int i=0;i<len;i++) {
			s1[i] = (s1[i] - 'a' + last) % SGZ + 'a';
		}
		last = PTE.query(l, r, s1, len);
		printf("%d\n",last);
	}
	return 0;
}

【BZOJ 4861】[BeiJing2017] 魔法咒语

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4861

解题报告

对于$L \le 100$的情况,我们定义$f_{i,j}$表示长度为$i$,在$ac$自动机上匹配到点$j$的答案
然后暴力转移就可以了,时间复杂度:$O(10^4L)$

对于其他的点,我们构造转移矩阵,用矩阵快速幂来优化
至于如何把长度为$2$的和为$1$的给统一起来?我们可以加一个点缓存一下
时间复杂度:$O(200^3 \log L)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 1000000007;

int n,m,L,len[109];
char s1[109][109],s2[109][109];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

class AC_Automaton{
	int cnt,ch[109][26],vis[109],fail[109];
	vector<int> G[109];
	queue<int> que;
	public:
		inline AC_Automaton() {
			cnt=1;
		}
		inline void insert(char *s) {
			int l = strlen(s + 1), w = 1;
			for (int i=1;i<=l;i++) {
				int c = s[i] - 'a';
				if (!ch[w]) ch[w] = ++cnt;
				w = ch[w];
			}
			vis[w] = 1;
		}
		inline void build() {
			for (int i=0;i<26;i++) {
				if (!ch[1][i]) ch[1][i] = 1;
				else fail[ch[1][i]] = 1, que.push(ch[1][i]);
			}
			while (!que.empty()) { 
				int w = que.front(); que.pop(); 
				G[fail[w]].push_back(w);
				for (int i=0;i<26;i++) {
					if (ch[w][i] && ch[w][i] != 1) {
						que.push(ch[w][i]);
						fail[ch[w][i]] = ch[fail[w]][i];
					} else {
						ch[w][i] = ch[fail[w]][i];
					}
				}
			} 
			DFS(1, 0);
		}
		inline int size() {
			return cnt;
		}
		inline int MOVE(int w, int j) {
			if (vis[j]) return -1;
			for (int i=1;i<=len[w];i++) {
				j = ch[j][s1[w][i]-'a'];
				if (vis[j]) return -1;
			}
			return j;
		}
	private:
		void DFS(int w, int t) {
			t |= vis[w];
			if (t) vis[w] = 1; 
			for (int i=G[w].size()-1;~i;i--) {
				if (G[w][i] != i) { 
					DFS(G[w][i], t);
				}
			}
		}
}ac;

namespace SUBTASK_ONE{
	int f[109][109],tot,ans;
	int tra[109][109];
	
	inline void solve() {
		for (int i=1;i<=n;i++) {
			scanf("%s",s1[i]+1);
			len[i] = strlen(s1[i]+1);
		}
		for (int i=1;i<=m;i++) {
			scanf("%s",s2[i]+1);
			ac.insert(s2[i]);
		}
		ac.build(); 
		for (int i=1;i<=n;i++) {
			for (int j=1;j<=ac.size();j++) {
				int tmp = ac.MOVE(i, j);
				if (tmp != -1) tra[j][i] = tmp; 
			}
		}
		f[0][1] = 1;
		for (int i=0;i<L;i++) {
			for (int j=1;j<=ac.size();j++) {
				if (f[i][j]) {
					for (int k=1,t1,t2;k<=n;k++) {
						if ((t1=tra[j][k]) != -1 && (t2=i + len[k]) <= L) {
							f[t2][t1] = (f[t2][t1] + f[i][j]) % MOD; 
						}
					}
				}
			}
		}
		for (int i=1;i<=ac.size();i++) {
			ans = (ans + f[L][i]) % MOD;
		}
		printf("%d\n",ans);
	} 
};

namespace SUBTASK_TWO{
	int sz,tot,tra[109][109*109+109];
	struct Matrix{
		int a[209][209];
		inline Matrix() {
			memset(a,0,sizeof(a));
		}
		inline Matrix(int x) {
			memset(a,0,sizeof(a));
			for (int i=1;i<=sz;i++) a[i][i] = x;
		}
		inline Matrix operator * (const Matrix &M) {
			Matrix ret;
			for (int i=1;i<=sz;i++) {
				for (int j=1;j<=sz;j++) {
					for (int k=1;k<=sz;k++) {
						ret.a[i][j] = (ret.a[i][j] + (LL)a[k][j] * M.a[i][k]) % MOD;	
					}
				}
			}
			return ret;
		}
		inline Matrix operator ^ (int t) {
			Matrix ret(1),tmp;
			for (int i=1;i<=sz;i++) {
				memcpy(tmp.a[i],a[i],sizeof(a[i]));
			}
			for (;t;t>>=1,tmp=tmp*tmp) {
				if (t&1) ret = ret * tmp;
			}
			return ret;
		}
		inline void init() {
			memset(a,0,sizeof(a));
		}
	}ans,trans;
	
	inline void solve() {
		for (int i=1;i<=n;i++) {
			scanf("%s",s1[i]+1);
			len[i] = strlen(s1[i]+1);
		}
		for (int i=1;i<=m;i++) {
			scanf("%s",s2[i]+1);
			ac.insert(s2[i]);
		}
		ac.build(); sz = ac.size();
		for (int i=1;i<=n;i++) {
			for (int j=1;j<=sz;j++) {
				int tmp = ac.MOVE(i, j);
				if (tmp != -1) tra[j][i] = tmp; 
			}
		}
		ans.a[1][1] = 1; int ori = sz; 
		for (int i=1;i<=ori;i++) trans.a[i][++sz]++;
		for (int i=1;i<=ori;i++) {
			for (int j=1;j<=n;j++) {
				if (!tra[i][j]) continue;
				if (len[j] == 1) ++trans.a[tra[i][j]][i];
				else trans.a[tra[i][j]+ori][i]++;
			}
		}
		trans = trans ^ L;
		ans = ans * trans;
		int vout = 0;
		for (int i=1;i<=ori;i++) vout = (vout + ans.a[i][1]) % MOD;
		cout<<vout<<endl;
	}
};

int main() {
	n = read(); m = read(); L = read();
	if (L <= 100) {
		SUBTASK_ONE::solve();
	} else {
		SUBTASK_TWO::solve();
	}
	return 0;
}

【BZOJ 3103】[ONTAK2010] Palindromic Equivalence

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3103
神犇题解:http://foreseeable97.logdown.com/posts/194507-herbicidalontak2010palindromic-equivalence

解题报告

这些字符串相关的计数题已经做过很多了吧?
这题显然就是给定$O(n)$个相等与不等的关系,让你求染色方案数
这样直接做好像是一个$NP$的问题?就是四色定理那个一般化后的问题

但这题有一个非常好的性质,如果我们把一个等价类看成点,不等关系看成边
那么每一个联通块都是一个完全图!也就是一个弦图!
弦图的染色方案数是可以使用完美消除序列在$O(n)$的时间复杂度内解决的
有因为这题是完全图,所以任意一个$1 \sim n$的排列都是完美消除序列
于是直接从$1 \to n$进行计算即可

至于这图是个弦图图的证明,想一想还是很简单的(虽然不怎么容易观察出来)
我们可以参考:http://foreseeable97.logdown.com/posts/194507-herbicidalontak2010palindromic-equivalence

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 2000009;
const int M = N << 1;
const int MOD = 1000000007;

char pat[N],s[N];
int n,ans=1,fa[N],rid[N],col[N];
int vis[N],head[N],nxt[M],to[M]; 
vector<pair<int,int> > e;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int find(int x) {
	return x == fa[x]? x: fa[x] = find(fa[x]);
}

inline void manacher() {
	for (int i=1,r=1,p=1,t;i<=n*2;i++) {
		t = min(r - i, rid[p - (i - p)]);
		while (s[i+t+1] == s[i-t-1]) t++, fa[find(i+t)] = find(fa[i-t]);
		if ((rid[i] = t) + i > r) r = t + i, p = i;
		e.push_back(make_pair(i - t - 1, i + t + 1));
	}
}

inline void AddEdge(int u, int v) {
	static int E = 1; 
	if (u == v || !(u & 1) || !(v & 1)) return;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

int main() {
	scanf("%s",pat+1); n = strlen(pat+1); 
	s[0] = '#'; s[n*2] = '@';
	for (int i=1;i<=n;i++) s[i*2-1] = pat[i], s[i*2] = '*';
	for (int i=1;i<=n*2;i++) fa[i] = i;
	manacher();
	for (int i=0;i<e.size();i++) AddEdge(find(e[i].first), find(e[i].second));
	for (int i=1,cnt;cnt=26,i<=n*2;i+=2) {
		if (find(i) != i) continue; col[i] = 1;
		for (int j=head[i];j;j=nxt[j]) {
			if (col[to[j]] && vis[to[j]] < i) 
				--cnt, vis[to[j]] = i;
		}  
		if (cnt <= 0) ans = 0; 
		else ans = (LL)ans * cnt % MOD;
	}
	cout<<ans;
	return 0;
}

—————————— UPD 2017.4.26 ——————————
今天我们机房讨论了一下,这货是个弦图,不一定是一个完全图

【BZOJ 4231】回忆树

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4231
数据生成器:http://paste.ubuntu.com/24366714/
神犇题解:http://www.cnblogs.com/clrs97/p/5467637.html

解题报告

首先我们如果最终一个串出现的位置会越过$LCA$
那么我们可以把这一部分的情况单独拿出来,暴力跑$KMP$

剩下就是单纯地从根节点向下,或者向上的路径中出现了多少次
这不难让我们想到广义后缀自动机,但似乎这题并不能用

考虑另一个方法,把所有模式串建成AC自动机
然后在原树上$DFS$,进入一个点时将其在AC自动机对应的结点权值$+1$
退出来的时候将其$-1$,那么我们在需要询问的时候统计一下子树的权值和就可以了

总时间复杂度:$O(n \log n + \sum |S|)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int M = 600009;

int n,m,head[N],nxt[M],to[M],cost[M],U[N];
int pp[N][2],ans[N],dep[N],fa[N][20],C[N];
vector<pair<int,int> > qry[N]; 

class AC_Automaton{
	int dfs_cnt,ch[M][26],fail[M],in[M],out[M];
	queue<int> que; vector<int> sn[M]; 
	struct Fenwick_Tree{
		int sum[M],sz;
		inline int lowbit(int x) {return x & -x;}
		inline void modify(int w, int delta) {
			for (int i=w;i<=sz;i+=lowbit(i)) sum[i] += delta;
		}
		inline int query(int l, int r) {
			int ret = 0; l--;
			for (int i=l;i;i-=lowbit(i)) ret -= sum[i];
			for (int i=r;i;i-=lowbit(i)) ret += sum[i];
			return ret;
		}
	}BIT;
	public:
		inline void build() {
			for (int i=0;i<26;i++) ch[0][i]=1;
			que.push(1); fail[1] = 0;
			while (!que.empty()) {
				int w = que.front(); que.pop();
				sn[fail[w]].push_back(w);
				for (int i=0;i<26;i++) {
					if (ch[w][i]) {
						que.push(ch[w][i]);
						fail[ch[w][i]] = ch[fail[w]][i];
					} else ch[w][i] = ch[fail[w]][i];
				}
			}
			DFS(1);
			BIT.sz = dfs_cnt;
		}
		inline int insert(char *s) {
			static int cnt = 1;
			int w = 1, len = strlen(s+1);
			for (int i=1,c;i<=len;i++) {
				if (!ch[w]-'a']) ch[w] = ++cnt;
				w = ch[w]; 
			} 
			return w;
		}
		inline int query(int p) {
			return BIT.query(in[p], out[p]);
		}
		inline void modify(int p, int delta) {
			BIT.modify(in[p], delta);
		}
		inline int move(int w, int c) {
			return ch[w];
		}
	private:
		void DFS(int w) {
			in[w] = ++dfs_cnt;
			for (int i=sn[w].size()-1;~i;i--)
				if (!in[sn[w][i]]) DFS(sn[w][i]);
			out[w] = dfs_cnt;
		}
}ac;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void AddEdge(int u, int v, int c) {
	static int E = 1; cost[E+1] = cost[E+2] = c;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

inline int LCA(int a, int b) {
	if (dep[a] < dep[b]) swap(a, b);
	for (int j=19;~j;j--) if (dep[fa[a][j]] >= dep[b]) a = fa[a][j];
	if (a == b) return a;
	for (int j=19;~j;j--) if (fa[a][j] != fa[b][j]) a = fa[a][j], b = fa[b][j];
	return fa[a][0];
}

void pre(int w, int f) { 
	fa[w][0] = f; dep[w] = dep[f] + 1;
	for (int i=head[w];i;i=nxt[i]) if (to[i] != f) 
		C[to[i]] = cost[i], pre(to[i], w);
}

void solve(int w, int p) { 
	for (int i=qry[w].size()-1,f;~i;i--) {
		if (qry[w][i].first>0) f = 1; else f = -1, qry[w][i].first *= -1;
		ans[qry[w][i].first] += ac.query(pp[qry[w][i].first][qry[w][i].second]) * f;
	}
	for (int i=head[w],tmp;i;i=nxt[i]) {
		if (dep[to[i]] > dep[w]) {
			tmp = ac.move(p, cost[i]); 
			ac.modify(tmp, 1); 
			solve(to[i], tmp);
			ac.modify(tmp, -1); 
		}
	}
}

inline int dif(int &u, int &v, int lca, char *s, int len) {
	static char ss[M]; static int NXT[M]; int tot = 0, TOT;
	int w = u, l = dep[u] - dep[lca] - len + 1, ret = 0;
	if (l > 0) {for (int j=0;l;l>>=1,++j) if (l&1) w = fa[w][j]; u = w;} 
	while (w != lca) ss[++tot] = C[w] + 'a', w = fa[w][0];
	w = v; l = dep[v] - dep[lca] - len + 1;
	if (l > 0) {for (int j=0;l;l>>=1,++j) if (l&1) w = fa[w][j]; v = w;}
	TOT = (tot += dep[w] - dep[lca]);
	while (w != lca) ss[tot--] = C[w] + 'a', w = fa[w][0];
	
	for (int i=1,w;i<=len;i++) {
		for (w=NXT[i];w&&s[w+1]!=s[i+1];w=NXT[w]);
		NXT[i+1] = w + (s[w+1] == s[i+1]);
	}
	for (int i=1,w=0;i<=TOT;i++) {
		for (;w&&s[w+1]!=ss[i];w=NXT[w]);
		w += s[w+1] == ss[i];
		ret += w == len;
	} 
	return ret;
}

int main() {
	n = read(); m = read();
	for (int i=1,u,v;i<n;i++) {
		u = read(); v = read();
		char c[2]; scanf("%s",c);
		AddEdge(u, v, c[0] - 'a');
	} 
	pre(1, 1); 
	for (int j=1;j<=19;j++) 
		for (int i=1;i<=n;i++) 
			fa[i][j] = fa[fa[i][j-1]][j-1];
	char pat[300009];
	for (int i=1,u,v,lca,ll,p1,p2;i<=m;i++) {
		U[i] = u = read(); v = read(); lca = LCA(u, v);
		scanf("%s",pat+1); pp[i][0] = ac.insert(pat); ll = strlen(pat+1);
		qry[u].push_back(make_pair(i,1)); qry[v].push_back(make_pair(i,0)); 
		ans[i] += dif(u, v, lca, pat, ll); 
		qry[u].push_back(make_pair(-i,1)); qry[v].push_back(make_pair(-i,0));
		for (int l=1,r=ll;l<r;l++,r--) swap(pat[l], pat[r]); pp[i][1] = ac.insert(pat);
	} 
	ac.build();
	solve(1, 1);
	for (int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}

【51NOD 1154】回文串划分

相关链接

题目传送门:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1154
数据生成器:http://paste.ubuntu.com/24310870/

解题报告

可以用鏼爷今年WC讲的技巧把时间复杂度优化到$O(n \log n)$
为了好写,我套了一个$PAM$,不过鏼爷讲直接维护就可以了

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1000000;
const int SGZ = 26;
const int INF = 1e9;

class Palindromic_Tree{
	int tot,cnt,last,fail[N],len[N],ch[N][SGZ];
	int dif[N],nxt[N],ans[N],f[N];
	public:
		inline int build(char *s) {
			fail[0] = fail[1] = cnt = last = 1; 
			tot = strlen(s); len[1] = -1; 
			for (int i=0;i<tot;i++) {
				insert(s, i, s[i]-'a');
				update(i);
			}
			return ans[tot-1];
		}
	private:
		inline void insert(char *s, int p, int c) {
			int w = last;
			for (;s[p-len[w]-1]!=s[p];w=fail[w]);
			if (!ch[w]) {
				int nw=++cnt, t=fail[w]; len[nw] = len[w] + 2;
				for (;s[p-len[t]-1]!=s[p];t=fail[t]);
				fail[nw] = ch[t]; ch[w] = nw;
				
				dif[nw] = len[nw] - len[fail[nw]];
				if (dif[nw] == dif[fail[nw]]) nxt[nw] = nxt[fail[nw]];
				else nxt[nw] = fail[nw];	
			} 
			last = ch[w]; 
		}
		inline void update(int cur) {
			ans[cur] = INF;
			for (int w=last;len[w]>0;w=nxt[w]) {
				f[w] = ans[cur-len[nxt[w]]-dif[w]] + 1;
				if (dif[w] == dif[fail[w]]) f[w] = min(f[w], f[fail[w]]);
				ans[cur] = min(ans[cur], f[w]);
			}
		}
}PAM;

int main() {
	char pat[N]; cin>>pat;
	cout<<PAM.build(pat);
	return 0;
}

【BZOJ 4650】[NOI2016] 优秀的拆分

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4650
神犇题解:https://blog.sengxian.com/solutions/bzoj-4650

解题报告

主要是统计以每个点为开头/结尾的能划分成两个相等子串的串有多少个
这个是SA的经典应用

当然问能划分成x个相同子串的问题,SA也是一样的做法
比如:https://www.codechef.com/problems/TANDEM

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 60009;
const int SGZ = 26;
const int M = 15;

char pat[N];
int n,c1[N],c2[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

class Suffix_Array{
	char s[N]; int *rak,*que,len,dif;
	int arr1[N],arr2[N],bot[N],sa[N],height[N];
	class Sparse_Table{
		int mn[N][M],len;
		public:
			inline void init(int LEN, int *height) {
				len = LEN; memset(mn,0,sizeof(mn));
				for (int i=1;i<=len;i++) mn[i][0] = height[i];
				for (int j=1,w=1;j<M;j++,w<<=1) {
					for (int i=1,l=len-w;i<=l;i++) {
						mn[i][j] = min(mn[i][j-1], mn[i+w][j-1]);
					}
				} 
			}
			inline int query(int l, int r) {
				if (l > r) swap(l, r); ++l;
				int h = r - l + 1 >> 1, t = 0, L = 1;
				while (L <= h) L<<=1, t++;
				return min(mn[l][t],mn[r-L+1][t]);
			}
	}st;
	public:
		inline void init(char *S, int L) {
			memset(s,0,sizeof(s));
			memset(arr1,0,sizeof(arr1));
			memset(arr2,0,sizeof(arr2));
			for (int i=1;i<=L;i++) s[i] = S[i];
			len = L; build();
		}
		inline int query(int l, int r) {
			if (l < 0 || l > len || r < 0 || r > len) return 0;
			else return st.query(rak[l], rak[r]);
		}
		inline void out() {
			cout<<"----------"<<endl;
			for (int i=1;i<=len;i++) printf("%d ",sa[i]); cout<<endl;
			for (int i=1;i<=len;i++) printf("%d ",height[i]); cout<<endl;
			cout<<"----------"<<endl;
		}
	private:
		inline void build() {
			rak = arr1; que = arr2;
			for (int i=1;i<=SGZ;i++) bot[i] = 0;
			for (int i=1;i<=len;i++) bot[s[i]-'a'+1]++;
			for (int i=2;i<=SGZ;i++) bot[i] += bot[i-1];
			for (int i=1;i<=len;i++) sa[bot[s[i]-'a'+1]--] = i;
			rak[sa[1]] = dif = 1;
			for (int i=2;i<=len;i++) rak[sa[i]] = (dif += (s[sa[i]]!=s[sa[i-1]]));
			for (int l=1,tot;tot=0,l<=len;l<<=1) {
				for (int i=len-l+1;i<=len;i++) que[++tot] = i;
				for (int i=1;i<=len;i++) if (sa[i] > l) que[++tot] = sa[i] - l;
				for (int i=1;i<=dif;i++) bot[i] = 0;
				for (int i=1;i<=len;i++) bot[rak[i]]++;
				for (int i=2;i<=dif;i++) bot[i] += bot[i-1];
				for (int i=len;i;i--) sa[bot[rak[que[i]]]--] = que[i];
				swap(que, rak); rak[sa[1]] = dif = 1;
				for (int i=2;i<=len;i++) 
					if (que[sa[i]]==que[sa[i-1]]&&que[sa[i]+l]==que[sa[i-1]+l]) rak[sa[i]]=dif;
					else rak[sa[i]] = ++dif;
				if (dif >= len) break;
			} 
			for (int i=1;i<=len;i++) {
				int t = max(0, height[rak[i-1]] - 1);
				int p1 = i + t, p2 = sa[rak[i]-1] + t;
				for (;s[p1]==s[p2];p1++,p2++) ++t;
				height[rak[i]] = t;
			}
			st.init(len, height);
		}
}dir,rev; 

int main() {
	for (LL T=read(),vout;vout=0,T;T--) {
		memset(c1,0,sizeof(c1)); memset(c2,0,sizeof(c2));
		scanf("%s",pat+1); n = strlen(pat+1);
		dir.init(pat, n); 
		for (int i=1,j=n;i<j;i++,j--) swap(pat[i], pat[j]);
		rev.init(pat, n);
		for (int l=1,suf,pre,L,R;l<=n;l++) {
			for (int i=1;i<=n;i+=l) {
				suf = dir.query(i, i+l); 
				pre = rev.query(n-i+2, n-i-l+2) + 1;
				L = max(i, i + l - pre);
				R = min(i + l - 1, i + suf - 1);
				if (L <= R) {
					c1[L+l]++; c1[R+l+1]--;
					c2[L-l]++; c2[R-l+1]--;
				}
			}
		}
		for (int i=1,t1=c1[0],t2=c2[0];i<=n;i++) {
			t1 += c1[i]; t2 += c2[i];
			vout += (LL)t1 * t2;
		}
		printf("%lld\n",vout);
	}
	return 0;
}

【日常小测】图片加密

题目大意

给定两个数字串$A,B$,长度分别为$n,m(m \le n \le 250000)$
串中的元素为$<512$的自然数,你可以花费一个单位的代价改变一个元素在二进制下的最低位
询问能否通过修改操作使得$B$在$A$中出现
如果可以,请输出最小的花费和在花费最小的前提下最左边的匹配位置

解题报告

我们发现高位不可改,于是我们用$KMP$统计一下高位的合法位置
至于低位,我们可以拆成两次$FFT$
于是搞一搞就可以了

至于为什么我写的是$SA$?
因为考场上忘掉$KMP$怎么写了 QwQ

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 550000;
const int M = N << 1;
const int INF = 1e9;
const int MOD = 1004535809;
 
int n,m,L,a1[M],a2[N],o1[N],o2[N],leg[N],ans[N]; 
  
inline int read() {
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret*f;
}
 
inline int Read() {
    static char pat[20]; scanf("%s",pat+1); int ret = 0;
    for (int i=8,w=1;i;i--,w<<=1) ret += (pat[i]-'0') * w; 
    return ret;
}
 
 
class Suffix_Array{
    int len,tot,*rak,*que,bot[N],sa[M],arr1[M],arr2[M],height[N];
    public:
        inline void build() {
            rak = arr1; que = arr2; len = n + m + 1;
            a1[0] = -1; a1[len+1] = -2;
            for (int i=1;i<=len;i++) ++bot[a1[i]];
            for (int i=1;i<=100000;i++) bot[i] += bot[i-1];
            for (int i=1;i<=len;i++) sa[bot[a1[i]]--] = i;
            rak[sa[1]] = tot = 1;
            for (int i=2;i<=len;i++) rak[sa[i]] = (a1[sa[i]]==a1[sa[i-1]])? tot: ++tot;
            for (int l=1,cnt;cnt=0,l<=len;l<<=1) {
                for (int i=len-l+1;i<=len;i++) que[++cnt] = i;
                for (int i=1;i<=len;i++) if (sa[i]>l) que[++cnt] = sa[i] - l;
                for (int i=0;i<=tot;i++) bot[i] = 0;
                for (int i=1;i<=len;i++) bot[rak[i]]++;
                for (int i=1;i<=tot;i++) bot[i] += bot[i-1];
                for (int i=len;i;i--) sa[bot[rak[que[i]]]--] = que[i];
                swap(que, rak); rak[sa[1]] = tot = 1;
                for (int i=2;i<=len;i++) 
                    if (que[sa[i]]==que[sa[i-1]]&&que[sa[i]+l]==que[sa[i-1]+l]) rak[sa[i]] = tot;
                    else rak[sa[i]] = ++tot;
                if (tot >= len) break;
            }
            GetHeight();
        }
        inline void solve() {
            for (int i=rak[n+2];height[i]>=m;i--) if (sa[i] <= n) leg[sa[i]] = 1;
            for (int i=rak[n+2]+1;height[i]>=m;i++) if (sa[i] <= n) leg[sa[i]] = 1;
        }
    private:
        inline void GetHeight() {
            for (int i=1;i<=len;i++) {
                int len = max(0, height[rak[i-1]] - 1);
                int p1 = i + len, p2 = sa[rak[i]-1] + len;
                while (a1[p1++] == a1[p2++]) len++;
                height[rak[i]] = len;
            }
        }
}SA;
 
class Number_Theoretic_Transform{
    int pos[M],REV,G;
    public:
        inline void init() {
            for (L=1;L<n+m;L<<=1); G = 3;
            int len = 1,tt=-1; while (len < L) len<<=1, ++tt; REV = Pow(L, MOD-2);
            for (int i=1;i<len;i++) pos[i] = (pos[i>>1]>>1)|((1<<tt)*(i&1));
        }
        inline void trans(int *a, int t=1) {
            for (int i=0;i<L;i++) if (pos[i] < i) swap(a[pos[i]], a[i]);
            for (int l=2;l<=L;l<<=1) {
                int wn = Pow(G, MOD/l); if (t == -1) wn = Pow(wn, MOD-2);
                for (int i=0;i<L;i+=l) {
                    for (int j=0,w=1;j<l/2;j++,w=(LL)w*wn%MOD) {
                        int tmp = (LL)w * a[i+l/2+j] % MOD;
                        a[i+l/2+j] = (a[i+j] - tmp) % MOD;
                        a[i+j] = (a[i+j] + tmp) % MOD;
                    }
                }
            }
            if (t == -1) for (int i=0,rev=Pow(L,MOD-2);i<L;i++) a[i] = (LL)a[i] * rev % MOD; 
            for (int i=0;i<L;i++) a[i] = a[i]<0? a[i] + MOD: a[i];
        } 
    private:
        inline int Pow(int w, int t) {
            int ret = 1;
            for (;t;t>>=1,w=(LL)w*w%MOD)
                if (t&1) ret=(LL)ret*w%MOD;
            return ret;
        }
}NTT;
 
int main() {
    n = read(); m = read();
    for (int i=1;i<=n;i++) a1[i] = o1[i] = Read();
    for (int i=1;i<=m;i++) a2[i] = o2[i] = Read();
     
    //find out legal positions
    for (int i=1;i<=m;i++) a1[n+i+1] = a2[i];
    for (int i=1;i<=n+m+1;i++) a1[i] >>= 1, a1[i]++;
    a1[n+1] = 0; SA.build(); 
    SA.solve();
     
    //calculate the cost
    NTT.init();
    memset(a1,0,sizeof(a1)); memset(a2,0,sizeof(a2));
    for (int i=0;i<n;i++) a1[i] = o1[i+1] & 1;
    for (int i=0;i<m;i++) a2[i] = (o2[m-i] & 1) ^ 1;
    NTT.trans(a1); NTT.trans(a2);
    for (int i=0;i<L;i++) a1[i] = (LL)a1[i] * a2[i] % MOD;
    NTT.trans(a1, -1);
    for (int i=1;i<=n;i++) ans[i] = a1[i+m-2];
    memset(a1,0,sizeof(a1)); memset(a2,0,sizeof(a2));
    for (int i=0;i<n;i++) a1[i] = (o1[i+1] & 1) ^ 1;
    for (int i=0;i<m;i++) a2[i] = o2[m-i] & 1;
    NTT.trans(a1); NTT.trans(a2);
    for (int i=0;i<L;i++) a1[i] = (LL)a1[i] * a2[i] % MOD;
    NTT.trans(a1, -1);
    for (int i=1;i<=n;i++) ans[i] += a1[i+m-2];
     
    //output the answer
    int pos=-1, cost=INF;
    for (int i=1;i<=n;i++) if (leg[i] && ans[i] < cost) cost = ans[i], pos = i;
    if (!~pos) puts("No");
    else printf("Yes\n%d %d\n",cost,pos);
    return 0;
}

【BZOJ 4319】[CERC2008] Suffix Reconstruction

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4319
神犇题解:http://www.cnblogs.com/Skyminer/p/6414088.html

解题报告

之前在做这个题的时候就听说过这题
但当时想了一会儿,感觉不可做,以为是他们记错题目了 QwQ
今天居然看到原题了,但想了很久,还是只会$O(26 \cdot n \log{n})$

先来说说$O(26 \cdot n \log{n})$的做法吧!
我们可以从上到下单个字符填,就是尽量往小的填,填完以后$O(n)$验证一遍

我们考虑分出不同的地方,因为填了都是比他小的,所以如果冲突,那一定是之前的太大了
但之前的部分已经贪心尽量小地填了,所以之前的肯定不能改小了,只能把当前位改大

所以这么做是对的,时间复杂度:$O(26 \cdot n^2)$
不难发现$SA$数组上一定是一段连续的A,之后一段连续的B。后面也是这样
于是我们可以二分每一个字符地分界点,这样复杂度就是$O(26 \cdot n \log{n})$的了

正解的话,是$O(n)$的,仍然是从小到大贪心
我们考虑计算$height$数组时候那个Trick的正确性证明
如果$rank[sa[i]+1] > rank[sa[i+1]+1]$的话,那么$sa[i]$填的字符一定比$sa[i+1]$小
否则他俩相等也没有关系,因为后面还是会把他们区分出来
于是贪心就可以$O(1)$验证了,于是总的时间复杂度就是线性的了!

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 500009;

int n,sa[N],rak[N];
char ans[N];

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main() {
	n = read(); 
	for (int i=1;i<=n;i++) rak[sa[i]=read()]=i;
	ans[sa[1]] = 'a';
	for (int i=1,w='a';i<n;i++) (rak[sa[i]+1]>rak[sa[i+1]+1])? ans[sa[i+1]]=++w: ans[sa[i+1]]=w;
	if (ans[n] <= 'z') printf("%s",ans+1);
	else puts("-1");
	return 0;
}

【日常小测】Different Trips

题目大意

给定一棵$n(n \le 10^5)$个结点的树,每一个结点的特征值定义为这个结点的度
询问从根节点走到叶子结点的所有路径中本质不同的字符串的数量

解题报告

这题就是诸神眷顾的幻想乡的弱化版,撸一发广义SAM就可以了

不过GEOTCBRL考完之后给我们增加了一点姿势水平:

广义后缀自动机如果使用DFS建立的话,时间复杂度是$O($叶子结点深度和$)$的
如果使用BFS来建立的话,时间复杂度是$O(n \cdot$字符集大小$)$

这在15年刘研绎的集训队论文《后缀自动机在字典树上的拓展》中有详细的证明
其中还给出了构造极端数据的构造方法
所以这题字符集大小这么大的话,这样会T的
可能只有后缀数组才能做 QwQ

Code

这辣鸡代码是可以卡的,泥萌不要卡啊…….

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 2000009;
 
int n,head[N],nxt[N],to[N],in[N];
 
inline int read() {
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret*f;
}
 
inline void AddEdge(int u, int v) {
    static int E = 1; in[u]++; in[v]++;
    to[++E] = v; nxt[E] = head[u]; head[u] = E;
    to[++E] = u; nxt[E] = head[v]; head[v] = E;
}
 
class Suffix_Automaton{
    int tot,len[N],fail[N],vis;
    map<int,int> ch[N];
    public:
        inline Suffix_Automaton() {tot=1;}
        inline int insert(int t, int c) {
            if (ch[t]&&len[ch[t]]==len[t]+1) return ch[t];
            int w = ++tot; len[w] = len[t] + 1;
            for (;t&&!ch[t];t=fail[t]) ch[t] = w;
            if (!t) fail[w] = 1;
            else if (len[ch[t]] == len[t] + 1) fail[w] = ch[t];
            else {
                int nt = ++tot, pt = ch[t];
                ch[nt] = ch[pt]; len[nt] = len[t] + 1;
                fail[nt] = fail[pt]; fail[pt] = fail[w] = nt;
                for (;t&&ch[t]==pt;t=fail[t]) ch[t] = nt;
            } return w;
        }
        inline LL GetAns() {
            LL ret = 0;
            for (int i=2;i<=tot;i++)
                ret += len[i] - len[fail[i]];
            return ret;
        }
}SAM;
 
void DFS(int w, int f, int ins) {
    int nins = SAM.insert(ins, in[w]);
    for (int i=head[w];i;i=nxt[i]) {
        if (to[i] != f) {
            DFS(to[i], w, nins);
        }
    }
}
 
int main() {
    n = read();
    for (int i=1;i<n;i++) AddEdge(read(), read());
    DFS(1, 1, 1);
    printf("%lld\n",SAM.GetAns());
    return 0;
}