【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 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 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;
}

【CodeChef FAVNUM】Favourite Numbers

题目传送门:https://www.codechef.com/problems/FAVNUM
中文题面:number_dp_by_zky

这个题目还是挺好玩的!
数位DP配上AC自动机!别有一番风味!

然而这个傻Ⅹ的AC自动机写炸了
调试了3个小时! (╯‵□′)╯︵┻━┻

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

char pat[20];

namespace AC_Automaton{
	#define AC AC_Automaton
	LL f[20][2000][2];
	int ch[2000][10],tag[2000],cnt,fail[2000],sta[20];
	queue<int> que;
	
	inline void insert(char *s){
		int n = strlen(s+1), w = 0;
		for (int i=1,c;i<=n;i++) {
			c = s[i] - '0';
			if (!ch[w]) {
				ch[w] = ++cnt;
			}
			w = ch[w];
		}
		tag[w] = 1;
	}
	
	inline void Build(){
		for (int i=0;i<=9;i++) if (ch[0][i]) {
			que.push(ch[0][i]);
		}
		
		while (!que.empty()) {
			int w = que.front(); que.pop();
			for (int c=0;c<=9;c++) if (ch[w]) {
				int nv = ch[w], pv = fail[w];
				while (pv && !ch[pv]) pv = fail[pv];
				fail[nv] = ch[pv];
				tag[nv] |= tag[fail[nv]];
				que.push(nv);
			} else {
				ch[w] = ch[fail[w]];
			}
		}
	}
	
	LL DFS(int t, int w, bool lim, bool leg) {
		if (!t) {
			return leg;
		} else if (!lim && ~f[t][w][leg]) {
			return f[t][w][leg];
		} else {
			LL ret = 0;
			for (int i=0,ty=lim?sta[t]:9;i<=ty;i++) {
				ret += DFS(t-1, ch[w][i], lim&&i==sta[t], leg|tag[ch[w][i]]);
			}
			return lim? ret: f[t][w][leg] = ret;
		}
	}
	
	inline LL query(LL lim) {
		int cnt = 0;
		while (lim) {
			sta[++cnt] = lim % 10;
			lim /= 10;
		}
		memset(f,-1,sizeof(f));
		return DFS(cnt,0,1,0);
	}
};

int main(){	
	LL L,R,k,n,bas,w,stp;
	cin>>L>>R>>k>>n;
	for (int i=1;i<=n;i++) {
		scanf("%s",pat+1);
		AC::insert(pat);
	}
	
	AC::Build();
	k += AC::query(L - 1);
	if (AC::query(R) < k) {
		puts("no such number");
		exit(0);
	}
	
	stp = 1; w = L - 1; 
	while (stp < (R - L + 1)) stp <<= 1;
	while (stp) {
		if (AC::query(w + stp) < k) {
			w += stp;
		}
		stp >>= 1;
	}
	printf("%lld\n",w+1);
	return 0;
}

【Codeforces 696D】Legen…

题目传送门:http://codeforces.com/contest/696/problem/D
官方题解:http://codeforces.com/blog/entry/46031

这个题目,看一眼数据范围就知道是AC自动机+矩阵快速幂
所以剩下的唯一问题就是,我们重定义矩阵运算之后为何其仍然满足结合律?

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

const int N = 200+9;
const int SGZ = 27;
const int MX = 201;

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;
}

struct Matrix{
	LL a[N][N];
	inline Matrix() {memset(a,-1,sizeof(a));}
	inline Matrix(Matrix &v) {memcpy(this,&v,sizeof(v));}
	inline Matrix(int bas, int v) {memset(a,bas,sizeof(a));for (int i=1;i<=MX;i++) a[i][i]=v;}
	inline Matrix operator * (const Matrix &B) {
		Matrix ret; 
		for (int i=1;i<=MX;i++) for (int j=1;j<=MX;j++) for (int k=1;k<=MX;k++) 
			if (~a[k][j] && ~B.a[i][k]) ret.a[i][j] = max(ret.a[i][j], a[k][j] + B.a[i][k]);
		return ret;
	}
	inline Matrix operator ^ (LL t) {
		Matrix ret(-1,0), tmp(*this); while (t) {
			if (t & 1) ret = ret * tmp;
			tmp = tmp * tmp; t >>= 1;
		} return ret; 
	} 
}tran,ans;

namespace AC_Automaton{
	#define ATM AC_Automaton
	int ch[N][SGZ],fail[N],val[N],cnt=1,vis[N];
	queue<int> que;
	
	inline void Add(char *s, int v){
		int w = 1, n = strlen(s+1);
		for (int i=1;i<=n;i++) {
			int c = s[i] - 'a' + 1;
			if (!ch[w]) ch[w] = ++cnt;
			w = ch[w];
		} val[w] += v;	
	}
	
	inline void Get_Fail(){
		que.push(1); fail[0] = fail[1] = 1; 
		for (int i=1;i<SGZ;i++) ch[1][i] = ch[1][i]?ch[1][i]:1;
		while (!que.empty()) {
			int w = que.front(); que.pop();
			val[w] += val[fail[w]]; vis[w] = 1;
			for (int c=1;c<SGZ;c++) if (ch[w]) {
				int nw = fail[w];
				while (nw > 1 && !ch[nw]) nw = fail[nw];
				fail[ch[w]] = nw!=w?ch[nw]:1; 
				if (!vis[ch[w]]) que.push(ch[w]);
			} else ch[w] = ch[fail[w]];
		}
	}
	
	inline void Build_Matrix(){
		ans.a[1][1] = 0;
		for (int i=1;i<=cnt;i++)
			for (int c=1;c<SGZ;c++) 
				tran.a[ch[i]][i] = val[ch[i]];	
	}
}; 

int main(){
	int n,val[N]; LL T; char pat[N]; cin>>n>>T;
	for (int i=1;i<=n;i++) cin>>val[i];
	for (int i=1;i<=n;i++) scanf("%s",pat+1), ATM::Add(pat,val[i]);
	ATM::Get_Fail(); ATM::Build_Matrix(); tran = tran^T; 
	ans = ans * tran; LL vout = 0; 
	for (int i=2;i<=MX;i++) vout = max(vout, ans.a[i][1]);
	printf("%I64d\n",vout);
 	return 0;
}

—– UPD 2016.10.2 —–
今天问了一下鏼爷,鏼爷给了一个非常简洁的证明:
最短路问题可以写成矩阵形式(比如倍增Floyd)
然后最短路显然满足结合律
然后这题对于矩乘的定义岂不是和最短路一样?

—————————— UPD 2017.2.1 ——————————
这题后来问了问YYY,结果YYY暴力展开矩乘
似乎这样就可以知道是否满足结合律了
不过如果在考场上,直接拍一拍吧
如果不出错,那就假装他满足结合律吧?

【BZOJ 4567】[Scoi2016] 背单词

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

这个题,就AC自动机搞一搞就可以啦!
省选时的我都能A,这是真简单啊!

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define AC AC_Automata
#define LL long long
using namespace std;

LL vout = 0;
char pat[510000+9];

namespace AC_Automata{
	const int N = 510000+9;
	const int SIGMA_SIZE = 26;
	struct Node{int ch[SIGMA_SIZE],fail,last,vis;}p[N];
	int cnt,que[N],itr1,itr2;
	vector<int> G[N];
	
	int head[N],to[N],nxt[N];
	int TOT,tot,sz[N];
	
	inline void AddEdge(int u, int v){to[++TOT] = v; nxt[TOT] = head[u]; head[u] = TOT;}
	
	inline void insert(char *s){
		int len = strlen(s), w=0;
		for (int i=0;i<len;i++){
			int c = s[i] - 'a';
			if (!p[w].ch) w = p[w].ch = ++cnt;
			else w = p[w].ch;
		} p[w].vis++;
	}
	
	inline void GetFail(){
		itr1 = 0; itr2 = 1;
		for (int i=0;i<SIGMA_SIZE;i++)
			if (p[0].ch[i]) que[++itr1] = p[0].ch[i];
		
		while (itr2 <= itr1){
			int w = que[itr2++];
			if (p[w].vis) AddEdge(p[w].last, w);
			for (int i=0;i<SIGMA_SIZE;i++){
				if (p[w].ch[i]) {
					int nw = p[w].fail;
					while (nw && !p[nw].ch[i]) nw = p[nw].fail;
					p[p[w].ch[i]].fail = p[nw].ch[i];
					p[p[w].ch[i]].last = p[p[nw].ch[i]].vis ? p[nw].ch[i] : p[p[nw].ch[i]].last;
					que[++itr1] = p[w].ch[i];
				}
			} 
		}
	}
	
	void DFS(int w){
		sz[w] = 1;
		for (int i=head[w];i;i=nxt[i]) DFS(to[i]), sz[w] += sz[to[i]], G[w].push_back(sz[to[i]]);
		int len = G[w].size();
		sort(G[w].begin(), G[w].end());
		for (int i=0,sta=0;i<len;i++) vout += (LL)sta + 1LL, sta += (LL)G[w][i];
	}
};

int main(){
	int n; scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%s",pat), AC::insert(pat);
	AC::GetFail(); AC::DFS(0);
	printf("%lld",vout);
	return 0;
}

【POJ 2778】DNA Sequence

题目传送门:http://poj.org/problem?id=2778
数据生成器:http://paste.ubuntu.com/17964294/

说好久没写AC自动机+矩阵快速幂了,专门找了一道来练练手
果然wa了好久好久,不过欣慰的是AC自动机还勉强能写出来

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;

const LL MOD = 100000;
const int MAXN = 100+9;
const int SIGMA_SIZE = 4;

char pat[MAXN];
int N,m,lim,vout;

struct Matrix{
	LL a[109][109];
	
	Matrix(){}
	Matrix(int val){
		for (int i=1;i<=lim;i++)
			memset(a[i],0,sizeof(a[i]));
		for (int i=1;i<=lim;i++)
			a[i][i] = val;
	}
	
}A(0);

inline void Mul(Matrix &M1, Matrix &M2){
	 Matrix ret(0);
	 for (int i=1;i<=lim;i++)
	 	for (int j=1;j<=lim;j++)
	 		for (int k=1;k<=lim;k++) ret.a[i][j] = (ret.a[i][j]+M1.a[k][j]*M2.a[i][k])%MOD; M1 = ret; } inline void Matrix_pow(Matrix &M, int t){ Matrix tmp(1); while (t) { if (t & 1) Mul(tmp, M); Mul(M,M); t >>= 1;
	}
	M = tmp;
}

namespace AC_Automaton{
	#define AC AC_Automaton
	int ch[MAXN][SIGMA_SIZE],get[MAXN];
	int fail[MAXN],cnt=1;
	int que[MAXN],frt,bak;
	
	inline int ord(char c){
		if (c=='A') return 0;
		else if (c=='T') return 1;
		else if (c=='C') return 2;
		else return 3;
	}
	
	inline void insert(char *s){
		int n = strlen(s+1), w = 1;
		for (int i=1,c;i<=n;i++){
			c = ord(s[i]);
			if (!ch[w]) ch[w] = ++cnt;
			w = ch[w];
		}
		get[w]=1;
	}
	
	inline void GetFail(){
		fail[1] = 1; bak=1; lim = cnt; 
		for (int i=0;i<SIGMA_SIZE;i++) if (ch[1][i]) que[++frt]=ch[1][i], fail[ch[1][i]]=1; while (frt >= bak){
			int w = que[bak++]; if (get[fail[w]]) get[w]=1;
			for (int c=0;c<SIGMA_SIZE;c++)if(ch[w]){ int nw = fail[w]; if (get[w]) get[ch[w]] = 1; while (!ch[nw] && nw>1) nw = fail[nw];
				if (!ch[nw]) fail[ch[w]] = nw;
				else fail[ch[w]] = ch[nw];
				que[++frt] = ch[w]; 
			}
		}
	}
	
	inline void Build_Matrix(){
		que[frt=1]=1; bak=1;
		while (frt >= bak){
			int w = que[bak++];
			for (int c=0;c<SIGMA_SIZE;c++)if(ch[w]){ if (!get[ch[w]]) A.a[ch[w]][w]++, que[++frt] = ch[w]; } else { int nw = fail[w]; while (!ch[nw] && nw>1) nw=fail[nw];
				if (ch[nw]) nw = ch[nw]; 
				if (!get[nw]) A.a[nw][w]++;	
			}
		}
	}
};

int main(){
	scanf("%d%d",&N,&m);
	for (int i=1;i<=N;i++){
		scanf("%s",pat+1);
		AC::insert(pat);
	} 
	AC::GetFail();
	AC::Build_Matrix();
	
	Matrix_pow(A,m); 
	for (int i=1;i<=lim;i++)
		vout = (vout+A.a[i][1])%MOD;
	printf("%d\n",vout);
	
	return 0;
}