【日常小测】学外语

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/07/NOI2017-matthew99.pdf

解题报告

从$i$向$a_i$连边
不难发现这题就是求一个基环树森林与自身同构的情况
这个我们可以用$Hash$来搞一搞

Code

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

const int N = 1000009;
const int MOD = 1000000007;
const int INF = 2e9;

int n, E, ans, head[N], nxt[N], to[N];
int inv[N], pw[N], ipw[N], pw23[N], R1[N], R2[N];
int pre[N], dep[N], in[N], deg[N], vis[N];

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

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

inline void AddEdge(int u, int v) {
	in[v]++; deg[v]++; pre[u] = v;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

inline void mrk(int w) {
	vis[w] = 1;
	if (--in[pre[w]] == 0) {
		mrk(pre[w]);
	}
}

inline int cal_node(int w) {
	int ret = R2[deg[w]];
	vector<int> arr;
	for (int i = head[w]; i; i = nxt[i]) {
		if (!in[to[i]]) {
			dep[to[i]] = dep[w] + 1;
			int tmp = cal_node(to[i]);
			arr.push_back(tmp);
			ret = (ret + (LL)R1[dep[w]] * tmp) % MOD;
		}
	}
	sort(arr.begin(), arr.end());
	for (int i = 0, j = 0; i < (int)arr.size(); i = j + 1) {
		for (; j + 1 < (int)arr.size() && arr[i] == arr[j + 1]; ++j);
		ans = (LL)ans * ipw[j - i + 1] % MOD;
	}
	return (LL)ret * ret % MOD;
}

inline int cal_cir(int w) {
	vector<int> node, arr;
	while (!vis[w]) {
		vis[w] = 1;
		node.push_back(w);
		for (int i = head[w]; i; i = nxt[i]) {
			if (in[to[i]]) {
				w = to[i];
				break;
			}
		}
	}
	for (int i = 0; i < (int)node.size(); i++) {
		dep[node[i]] = 6;
		arr.push_back(cal_node(node[i]));
	}
	int sta = 0, cnt = 1;
	for (int i = 0; i < (int)node.size(); i++) {
		sta = (sta + (LL)pw23[i] * arr[i]) % MOD;
	} 
	int ret = (LL)sta * pw23[n] % MOD;
	for (int i = 1, cur = sta; i < (int)node.size(); i++) {
		cur = (cur + (LL)arr[i - 1] * (pw23[i - 1 + node.size()] - pw23[i - 1])) % MOD;
		ret = min(ret, int((LL)cur * pw23[n - i] % MOD));
		cnt += ((cur = (cur + MOD) % MOD) == (LL)sta * pw23[i] % MOD);
	}
	ans = (LL)ans * inv[cnt] % MOD;
	return ret;
}

int main() {
	srand(19991216);
	inv[0] = pw[0] = ipw[0] = pw23[0] = 1;
	R1[0] = rand(); R2[0] = rand();
	for (int i = 1; i < N; i++) {
		pw[i] = (LL)pw[i - 1] * i % MOD;
		pw23[i] = pw23[i - 1] * 131ll % MOD;
		inv[i] = Pow(i, MOD - 2);
		ipw[i] = Pow(pw[i], MOD - 2);
		R1[i] = rand(); R2[i] = rand();
	}
	
	for (int T = read(); T; T--) {
		memset(head, 0, sizeof(head));
		memset(deg, 0, sizeof(deg));
		memset(vis, 0, sizeof(vis));
		memset(in, 0, sizeof(in));
		E = 0; ans = 1;
		
		n = read();
		for (int i = 1; i <= n; i++) {
			AddEdge(i, read());
		}	
		for (int i = 1; i <= n; i++) {
			if (!in[i] && !vis[i]) {
				mrk(i);
			}
		}
		vector<int> arr;
		for (int i = 1; i <= n; i++) {
			if (in[i] && !vis[i]) {
				arr.push_back(cal_cir(i));
			}
		}
		sort(arr.begin(), arr.end());
		for (int i = 0, j = 0; i < (int)arr.size(); i = j + 1) {
			for (; j + 1 < (int)arr.size() && arr[i] == arr[j + 1]; ++j);
			ans = (LL)ans * ipw[j - i + 1] % MOD;
		}
		ans = ((LL)ans * pw[n] - 1) % MOD;
		printf("%d\n", (ans + MOD) % MOD);
	}
	return 0;
}

【HDU 4623】Crime

相关链接

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=4623
神犇题解:http://blog.csdn.net/keshuai19940722/article/details/49455357

解题报告

脑袋里一直想着去年$ZJOI$的小星星
然后就各种优化,最后还是$T$成狗 QwQ

然后正解就是把每个数按照因数种类不同分组
最后搞下来只有$14$种不同的,然后暴力状压$DP$就可以了

Code

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

const int N = 3000000;
const int M = 16;

int n,mx,MX,MOD,f[N][M],cnt[M],bit[M],cur[M],sym[M],suf[M],leg[M][M];
int ty[]={0,1,2,3,2,4,5,6,2,3,7,8,5,9,10,11,2,1,5,1,7,12,13,1,5,4,14,3,10};

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 gcd(int a, int b) {
	return b? gcd(b, a%b): a;
}

inline void decode(int w, int *arr) {
	for (int i=mx;i;i--) {
		arr[i] = w % bit[i];
		w /= bit[i];
	}
}

inline int solve() {
	memset(cnt,0,sizeof(cnt));
	mx = MX = 0;
	for (int i=1;i<=n;i++) {
		cnt[ty[i]]++;
		mx = max(mx, ty[i]);
	}
	for (int i=1;i<=mx;i++) {
		bit[i] = cnt[i] + 1;
		MX = MX * bit[i] + cnt[i];
	}
	suf[mx] = 1;
	for (int i=mx-1;i;i--) {
		suf[i] = suf[i+1] * bit[i+1];
	}
	memset(f,0,sizeof(f));
	f[0][0] = 1;
	for (int i=0;i<MX;i++) {
		decode(i, cur);
		for (int j=0;j<=mx;j++) {
			if (!f[i][j]) continue;
			for (int k=1;k<=mx;k++) {
				if ((leg[k][j] || !j) && cur[k] < cnt[k]) {
					int to = i + suf[k];
					f[to][k] = (f[to][k] + (LL)f[i][j] * (cnt[k] - cur[k])) % MOD;
				}
			}
		}
	}
	int ret = 0;
	for (int i=1;i<=mx;i++) {
		ret = (ret + f[MX][i]) % MOD;
	}
	return ret;
}

int main() {
	for (int i=1;i<=28;i++) {
		if (sym[ty[i]]) continue;
		sym[ty[i]] = i;
	}
	for (int i=1;i<=14;i++) {
		for (int j=1;j<=14;j++) {
			if (gcd(sym[i], sym[j]) == 1) {
				leg[i][j] = 1;
			}
		} 
	}
	for (int T=read();T;T--) {
		n = read(); MOD = read();
		printf("%d\n",solve());
	}
	return 0;
}

【CodeChef TREEP】Period on tree

相关链接

题目传送门:https://www.codechef.com/NOV15/problems/TREEP
中文题面:http://www.codechef.com/download/translated/NOV15/mandarin/TREEP.pdf
官方题解:https://discuss.codechef.com/questions/76897/treep-editorial

题目大意

给定一个$n(n \le 200000)$个结点的树,每条边上有一个小写字母
定义$Str_{u,v}$为从$u$走到$v$将路径上的小写字母按顺序拼起来组成的字符串
给定$m(m \le 200000)$个操作,操作分两类:

  1. 输入$u,v$,询问$Str_{u,v}$的循环节最短为多长
  2. 输入$u,v,c$,表示将$u \to v$这条边上的字符改成$c$

解题报告

这么奇怪的题目,一看就只能是$Hash$来做
我们不难发现,若循环节为$l$,串长$len$,那么$\forall x \in (l,len]$若$x \equiv 0(\bmod l)$则$x$也是循环节
于是如果我们可以$O(\log n)$判定$l$是不是原串的循环节,我们就可以在$O(n \log^2 n)$的时间复杂度内解决这个问题了

我们发现,若是循环节,那么开头那一段的$Hash$值不仅可以整除整个串的$Hash$值,而且等于一个等比数列
于是我们就可以用BIT维护一个到根的前缀和,然后将判定优化到$O(\log n)$

Code

这是考试的代码,似乎没写多组数据,CC上交不了QwQ

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 200009;
const int M = N << 1;
const int SED = 37;
const int MOD = 1000000009;
 
int n,m,head[N],to[M],nxt[M],cost[M],dep[N],beg[N],END[N]; 
int POW[M],tot,pri[N],vis[N],sur[N],fa[N][20],val[N];
char pat[5];
 
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, 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;
}
 
class FenwickTree{
    #define lowbit(x) ((x)&(-(x)))
    int sum[N];
    public:
        inline void modify(int l, int r, int v) {
            for (int i=l-1;i;i-=lowbit(i)) sum[i] = (sum[i] - v) % MOD;
            for (int i=r;i;i-=lowbit(i)) sum[i] = (sum[i] + v) % MOD;
        }   
        inline int query(int p) {
            int ret = 0; p = beg[p];
            for (int i=p;i<=n;i+=lowbit(i)) 
                ret = (ret + sum[i]) % MOD;
            return (ret + MOD) % MOD;
        }
}up,dw;
 
inline void prework() {
    POW[0] = sur[1] = 1; 
    for (int i=1;i<M;i++) POW[i] = (LL)POW[i-1] * SED % MOD;
    for (int i=2;i<N;i++) {
        if (!vis[i]) pri[++tot] = i, sur[i] = i;
        for (int j=1;j<=tot&&i*pri[j]<N;j++) {
            vis[i*pri[j]] = 1; sur[i*pri[j]] = pri[j];
            if (i % pri[j] == 0) break;
        }
    }
}
 
inline int LCA(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int j=19;~j;j--) if (dep[fa[u][j]]>=dep[v]) u=fa[u][j];
    if (u == v) return u;
    for (int j=19;~j;j--) if (fa[u][j]!=fa[v][j]) u=fa[u][j],v=fa[v][j];
    return fa[u][0];
}
 
void DFS(int w, int f) {
    static int dfs_cnt = 0; 
    beg[w] = ++dfs_cnt;
    fa[w][0] = f; dep[w] = dep[f] + 1;
    for (int i=head[w];i;i=nxt[i]) {
        if (to[i] != f) {
            val[to[i]] = cost[i];
            DFS(to[i], w);
        }
    }
    END[w] = dfs_cnt;
    up.modify(beg[w], END[w], (LL)val[w] * POW[n-dep[w]+1] % MOD);
    dw.modify(beg[w], END[w], (LL)val[w] * POW[dep[w]] % MOD); 
}
 
inline int FA(int u, int k) {
    for (int t=0;k;k>>=1,t++) 
        if (k&1) u = fa[u][t];
    return u;
}
 
inline int query(int u, int v, int lca, int k) {
    if (dep[u] - dep[lca] >= k) {
        int ret = (up.query(u) - up.query(FA(u, k))) % MOD;
        return (((LL)ret * POW[dep[u]-1] % MOD) + MOD) % MOD;
    } else {
        int ret = (up.query(u) - up.query(lca)) % MOD;
        ret = (LL)ret * POW[dep[u] - 1] % MOD;
        int res = dep[u] + dep[v] - (dep[lca] << 1) - k;
        res = (dw.query(FA(v, res)) - dw.query(lca)) % MOD;
        res = (LL)res * POW[n + dep[u] - (dep[lca] << 1) - 1] % MOD;
        return ((res + ret) % MOD + MOD) % MOD;
    }
}
 
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;
}   
 
inline int query(int u, int v) {
    int lca = LCA(u, v); tot = 0;
    int len = dep[u] + dep[v] - (dep[lca] << 1);
    int STA = query(u, v, lca, len), ori = len;
    for (int c,w=len;c=sur[w],w>1;) {
        pri[++tot] = c; vis[tot] = 0;
        for (;w%c==0;w/=c) vis[tot]++; 
    }
    for (int i=1,sta,cur,PRI;i<=tot;i++) {
        PRI = pri[i];
        for (int j=1;j<=vis[i];j++) {
            sta = (LL)(Pow(POW[len/PRI], ori/len*PRI) - 1) * Pow(POW[len/PRI]-1, MOD-2) % MOD;
            cur = (LL)STA * Pow(query(u, v, lca, len / PRI), MOD-2) % MOD;
            if (sta==cur) len /= PRI;
            else break;
        }
    }
    return len;
}
 
int main() {
    prework();
    n = read(); 
    for (int i=1,u,v;i<n;i++) {
        u = read(); v = read();
        scanf("%s",pat+1);
        AddEdge(u, v, pat[1]-'a'+1);
    }
    DFS(1, 1);
    for (int j=1;j<20;j++) {
        for (int i=1;i<=n;i++) {
            fa[i][j] = fa[fa[i][j-1]][j-1];
        }
    } 
    m = read(); 
    for (int i=1,u,v,c;i<=m;i++) {
        if (read() == 1) {
            u = read(); v = read();
            printf("%d\n",query(u, v));
        } else {
            u = read(); v = read();
            if (dep[u] > dep[v]) swap(u, v);
            scanf("%s",pat+1); c = pat[1]-'a'+1;
            if (c == val[v]) continue;
            up.modify(beg[v], END[v], (LL)(c - val[v]) * POW[n-dep[v]+1] % MOD);
            dw.modify(beg[v], END[v], (LL)(c - val[v]) * POW[dep[v]] % MOD);
            val[v] = c;
        }
    } 
    return 0;
}

【日常小测】相似子串

题目大意

给定一棵$n(n \le 10^5)$的无根树,每条边上有一个字符
定义$str_{u,v}$为从$u$走到$v$,将边上的字符按顺序写下来得到的字符串
给定$m(m \le 10^5)$个询问,每一次询问会定义$k_i$种形如$a,b$这样的等价关系,意义为将所有的$a,b$字符视为同一个字符(关系具有传递性)
对于每一个询问还会给定$u_1,v_1,u_2,v_2$四个点,请你回答$str_{u_1,v_1}$与$str_{u_2,v_2}$是否至多有一个位置不匹配

解题报告

这种奇怪的匹配题目除了$FFT$之外,似乎只能$Hash$了吧?

我们先来考虑没有等价类,且是一条链的情况

定义$Hash$函数$f_{i,u,v}$为对于第$i$种字符来讲,$str_{u,v}$的$Hash$值
更进一步,$f_{i,u,v}=\sum\limits_{j=u}^{v}{[char_j=i] \cdot G^{j-u+1}}$
那么这两个字符串的$Hash$值只能在两种字符下不同,且这两种字符差的$G$的次幂相等

考虑快速求得$Hash$值,这个很简单,做一个前缀和就好
考虑快速求的差值对应的$G$的次幂,这个我们先预处理一下,然后扔到一个$map$里去就可以了
至此我们已经能在$O(|\sum|+\log n)$的时间复杂度内回答单个询问了

现在考虑加入等价类,这个我们可以将整个等价类的$Hash$值加起来一起比较就可以了
至于不是链的情况,那我们求个到根前缀和就能够解决问题啦!
至此我们已经在$O(n \log n + m (|\sum| + \log n))$的时间复杂度内解决了这个问题

【BZOJ 4373】算术天才⑨与等差数列

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4373
神犇题解:http://blog.csdn.net/TA201314/article/details/51177011

解题报告

首先,假如一个区间满足以下三个条件那么该区间一定合法:

$\%k$后相等
每一个数互不相同
区间和等于某一特定值

后两个条件都可以用线段树维护
问题就是第一个条件非常麻烦

先来考虑一种简单的Hash方式:记录区间的平方和
这样的话,我们可以$O(1)$计算基准值,$O(\log n)$判断是否等于基准值

但众所周知,Hash是不优雅的
于是我们可以先做一个差分序列,然后维护差分序列相邻两项的$\gcd$
考虑如果所有数的差都是$k$的整数倍,那么这些数$ \bmod \ k$之后肯定就相等啦!

另外的话,区间GCD配合差分的题,也不是第一次见了
之前NOI还考过一道:魔幻棋盘
以后和GCD相关的题目要想一想差分行不行啊!

【BZOJ 1414】[ZJOI2009] 对称的正方形

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

题号“1414”,还真的是把我做得“要死要死的”!做了一整天QAQ
Hash version:

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;
 
const int MX = 0;
const int MAXN = 2000+9;
unsigned int SEEDX = 37;
unsigned int SEEDY = 137;
 
int n,m; LL vout;
unsigned int px[2000+9],py[2000+9],mat[MAXN][MAXN],f[5][MAXN][MAXN];
 
inline int read(){
    char c=getchar(); int ret=0;
    while (c<'0'||c>'9') c=getchar();
    while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
    return ret;
}
 
inline void init(){
    m = read(); n = read(); vout = (unsigned int)n*m;
    for (int j=1;j<=m;j++) {
        for (int i=1;i<=n*2+1;i++) mat[i][j*2-1] = MX;
        for (int i=1;i<=n;i++) mat[i*2][j*2] = read(), mat[i*2-1][j*2] = MX;
        mat[n*2+1][j*2] = MX;
    } for (int i=1;i<=n*2+1;i++) mat[i][m*2+1] = MX;
    n = n*2+1; m = m*2+1;
}
 
inline void Hash_init(){
    px[0] = 1; for (int i=1;i<=2001;i++) px[i] = SEEDX*px[i-1];
    py[0] = 1; for (int i=1;i<=2001;i++) py[i] = SEEDY*py[i-1];
    for (int i=n,g=1;i;i--,g++) for (int j=1,h=1;j<=m;j++,h++) f[1][i][j] = px[g]*py[h]*mat[i][j] + f[1][i+1][j] + f[1][i][j-1] - f[1][i+1][j-1];
    for (int i=1,g=1;i<=n;i++,g++) for (int j=1,h=1;j<=m;j++,h++) f[2][i][j] = px[g]*py[h]*mat[i][j] + f[2][i-1][j] + f[2][i][j-1] - f[2][i-1][j-1];
    for (int i=1,g=1;i<=n;i++,g++) for (int j=m,h=1;j;j--,h++) f[3][i][j] = px[g]*py[h]*mat[i][j] + f[3][i-1][j] + f[3][i][j+1] - f[3][i-1][j+1];
    for (int i=n,g=1;i;i--,g++) for (int j=m,h=1;j;j--,h++) f[4][i][j] = px[g]*py[h]*mat[i][j] + f[4][i+1][j] + f[4][i][j+1] - f[4][i+1][j+1];
}
 
inline unsigned int Get_Hash(int t, int x1, int y1, int x2, int y2){
    if (t == 1) return (f[1][x1][y1] + f[1][x2+1][y2-1] - f[1][x2+1][y1] - f[1][x1][y2-1]) * px[2001-(n-x1+1)] * py[2001-y1];
    else if (t == 2) return (f[2][x1][y1] + f[2][x2-1][y2-1] - f[2][x2-1][y1] - f[2][x1][y2-1])* px[2001-x1] * py[2001-y1];
    else if (t == 3) return (f[3][x1][y1] + f[3][x2-1][y2+1] - f[3][x2-1][y1] - f[3][x1][y2+1]) * px[2001-x1] * py[2001-(m-y1+1)];
    else return (f[4][x1][y1] + f[4][x2+1][y2+1] - f[4][x2+1][y1] - f[4][x1][y2+1]) * px[2001-(n-x1+1)] * py[2001-(m-y1+1)];
}
 
inline bool judge(int x, int y, int len){
    unsigned int t1 = Get_Hash(1,x,y,x+len,y-len),t2 = Get_Hash(2,x,y,x-len,y-len);
    if (t1 != t2) return false;
    t1 = Get_Hash(3,x,y,x-len,y+len);
    if (t1 != t2) return false;
    t2 = Get_Hash(4,x,y,x+len,y+len);
    if (t1 != t2) return false;
    else return true;
}
 
inline void solve(){
    for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) if ((i&1) + (j&1) != 1) {
        int l=2,r=min(min(i-1,j-1),min(n-i,m-j)),ans=0,mid;
        while (l <= r) {
            mid = l + r >> 1;
            if (judge(i,j,mid)) l = mid+1, ans = mid;
            else r = mid-1;
        }vout += ans/2;
    }
}
 
int main(){
    init(); Hash_init(); solve();
    printf("%lld\n",vout);
    return 0;
}  

Manacher version:

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;
 
const int MAXN = 2000+9;
 
int mat[MAXN][MAXN],n,m,tmp[MAXN],ans[MAXN],que[MAXN],tot,pos[MAXN];
int res_x[MAXN][MAXN],res_y[MAXN][MAXN],sa_y[MAXN][MAXN],sa_x[MAXN][MAXN];
 
inline int read(){
    char c=getchar(); int ret=0;
    while (c<'0'||c>'9') c=getchar();
    while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
    return ret;
}
 
inline void manacher(int lim){
    int MX=0; ans[0] = 0;
    for (int i=1;i<=lim;i++) {
        if (MX+ans[MX] > i) ans[i] = min(MX+ans[MX]-i, ans[MX*2-i]);
        else ans[i] = 0;
        while (tmp[i+ans[i]+1] == tmp[i-ans[i]-1]) ans[i]++;
        if (ans[i]+i > MX+ans[MX]) MX = i;
    }
}
 
inline void DP(int lim){
    tot = 0; pos[0] = 0; int sta = 0;
    for (int i=1;i<=lim;i++) {
        while (tot && ans[i] <= que[tot]) tot--; sta = min(sta, tot);
        que[++tot] = ans[i]; pos[tot] = i; int w = sta;
        while (w < tot && min(que[w],(i-pos[w-1])*2-1) <= min(que[w+1],(i-pos[w])*2-1)) w++;
        sta = w; tmp[i] = min(que[w],(i-pos[w-1])*2-1);
    } 
}

int main(){
    m = read(); n = read();
    for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) mat[i*2][j*2] = read();
    n = n * 2 + 1; m = m * 2 + 1;
     
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) tmp[j] = mat[i][j]; tmp[0] = -1; tmp[m+1] = -2;
        manacher(m); 
        for (int j=1;j<=m;j++) sa_y[i][j] = ans[j];
    }
    for (int j=1;j<=m;j++) {
        for (int i=1;i<=n;i++) ans[i] = sa_y[i][j]*2+1;
        DP(n);
        for (int i=1;i<=n;i++) res_x[i][j] = tmp[i];
        for (int i=1;i*2<=n;i++) swap(ans[i],ans[n-i+1]);
        DP(n);
        for (int i=1;i<=n;i++) res_x[i][j] = min(res_x[i][j],tmp[n-i+1]);
    } 
         
    for (int j=1;j<=m;j++) {
        for (int i=1;i<=n;i++) tmp[i] = mat[i][j]; tmp[0] = -1; tmp[n+1] = -2;
        manacher(n); 
        for (int i=1;i<=n;i++) sa_x[i][j] = ans[i];
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++) ans[j] = sa_x[i][j]*2+1;
        DP(m);
        for (int j=1;j<=m;j++) res_y[i][j] = tmp[j];
        for (int j=1;j*2<=m;j++) swap(ans[j],ans[m-j+1]);
        DP(m);
        for (int j=1;j<=m;j++) res_y[i][j] = min(res_y[i][j], tmp[m-j+1]);
    } 
     
    LL vout = (n/2)*(m/2);
    for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) if ((i+j) % 2 == 0)
        vout += max(0,(min(res_x[i][j]-1,res_y[i][j]-1)/2)/2);
    printf("%lld\n",vout);
    return 0;
} 

【NOI六连测】[D2T3] 圈圈

题目传送门:http://pan.baidu.com/s/1pLvQmx1
离线版题目:http://paste.ubuntu.com/18302981/
数据传送门:http://pan.baidu.com/s/1dF0ovZj

这一道题,std是后缀树,然而被YYY踩了,居然一个Hash / SA就可捉QAQ
还是说正事吧。
对于每一次++,分两种情况讨论:
1)有至少一个数变成0:
对于这一种情况呢,明显,字典序最小的循环串的开头,只会在这些变成0的位置中产生
所以问题就变为:比较一些给定的字符串的大小。这个看起来也不是很能做的样子。
但如果我们只考虑两两比较,那么去掉这两个串的公共前缀,我们只需要比较一个字符就可以确定大小
所以拿SA / Hash处理出公共前缀后,比较单个字符的大小即可
2)没有数变成零:
对于这一种情况,答案不会变。水涨船高嘛!
于是这个题目就搞定啦!哎,这么简单!我这个纸张考试的时候怎么没有想到呢?QAQ
%%%YYY, Hash踩标程

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int MAXN = 200000+9;
const int SGZ = 51000;

int n,m,k,N,M,arr[MAXN],ord[MAXN],now,tot,ans;

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

inline bool cmp_sort(const int a, const int b){
	return arr[a] > arr[b];
}

namespace Suffix_Array{
	#define SA Suffix_Array
	int sa[MAXN],height[MAXN],t1[MAXN],t2[MAXN],bot[MAXN];
	int *tmp,*rank,m;
	
	namespace Sparse_Table{
		#define ST Sparse_Table
		int MN[MAXN][20];
		
		inline void init(){
			for (int i=1;i<=n;i++) MN[i][0]=height[i];
			for (int k=1;k<=16;k++)	for (int i=1;i<=n;i++)
				MN[i][k] = min(MN[i][k-1],MN[i+(1<<k-1)][k-1]); } inline int query(int l, int r){ if (l > r) swap(l,r); l++;
			int k=0,len=1,L=(r-l+1);
			while (len <= L/2) len*=2,k++;
			return min(MN[l][k],MN[r-len+1][k]);
		}
	};
	
	inline void GetHeight(){
		for (int i=1;i<=n;i++) if (rank[i]>1){
			int sta = max(0,height[rank[i-1]]-1);
			int p1=i+sta, p2=sa[rank[i]-1]+sta;
			while (arr[p1++]==arr[p2++]) sta++;
			height[rank[i]] = sta;
		}
	}
	
	inline void build(){
		tmp=t1; rank=t2; m=SGZ;
		for (int i=1;i<=m;i++) bot[i] = 0;
		for (int i=1;i<=n;i++) bot[tmp[i]=arr[i]+1]++;
		for (int i=2;i<=m;i++) bot[i] += bot[i-1];
		for (int i=n;i;i--) sa[bot[tmp[i]]--] = i;
		rank[sa[1]] = m = 1;
		for (int i=2;i<=n;i++)
			rank[sa[i]] = (tmp[sa[i]]==tmp[sa[i-1]])?m:++m;
			
		for (int k=1;k<=n;k*=2){ int T=0;
			for (int i=n-k+1;i<=n;i++) tmp[++T] = i;
			for (int i=1;i<=n;i++) if (sa[i] > k) tmp[++T] = sa[i]-k;
			for (int i=1;i<=m;i++) bot[i] = 0;
			for (int i=1;i<=n;i++) bot[rank[i]]++;
			for (int i=2;i<=m;i++) bot[i] += bot[i-1];
			for (int i=n;i;i--) sa[bot[rank[tmp[i]]]--] = tmp[i];
			
			swap(tmp,rank);
			rank[sa[1]] = m = 1;
			for (int i=2;i<=n;i++) if (tmp[sa[i]]==tmp[sa[i-1]]&&tmp[sa[i]+k]==tmp[sa[i-1]+k]) rank[sa[i]]=m; else rank[sa[i]] = ++m; if (m >= n) break;
		}
		GetHeight();
		ST::init();
	}
	
	inline int query(int a, int b){
		return ST::query(rank[a],rank[b]);
	}
};

int main(){
	freopen("cyclic.in","r",stdin);
	freopen("cyclic.out","w",stdout);
	scanf("%d%d%d",&N,&M,&k);
	for (int i=1;i<=N;i++) ord[i]=i,
		arr[i]=arr[i+N]=read();
	n = N*2; now = M-1; tot=1; SA::build();
	sort(ord+1,ord+1+N,cmp_sort);
	
	for (int i=1;i<=n;i++) if (SA::sa[i]<=N) {ans=SA::sa[i];break;}
	printf("%d\n",arr[ans+k-1]);
	for (int i=1;i<M;i++,now--){
		if (tot <= N && arr[ord[tot]]==now){
			ans = ord[tot++];
			while (tot <= N && arr[ord[tot]]==now){ int same = SA::query(ans, ord[tot]); int t = (arr[ans+same]+i)%M-(arr[ord[tot]+same]+i)%M; if (t >= 0) ans = ord[tot]; tot++;
			} printf("%d\n",(arr[ans+k-1]+i)%M);
		} else printf("%d\n",(arr[ans+k-1]+i)%M);	
	}
	
	return 0;
} 

【NOI六连测】[D2T1] 矩阵

题目传送门:http://pan.baidu.com/s/1pLvQmx1
离线版题目:http://paste.ubuntu.com/18292275/
数据传送门:http://pan.baidu.com/s/1dFDf8p7

哎呀,第一次看到这个题,一脸懵逼。之前在POJ上倒是做过矩阵的KMP,但这货没有模式串啊!
但是乱搞了一阵之后,如有神助般想到了二分+Hash,时间复杂度O(n^2*log(n))嗯,刚刚好!
于是就开始码Hash,码完之后不放心,还写了一个O(n^4)的SA来对拍,然后满心欢喜,终于可以A题啦!
然后被卡T了 QAQ, 只有暴力分QAQ, 然后今天就爆炸了,这题写了4h+啊!60分滚粗

下面说一点正事,这题正解也是Hash,那么能体现出优劣的就是Hash的方式了
Ⅰ.Sparse_Table版本http://paste.ubuntu.com/18292055/
在考试的时候YY出来的,提前处理出以每一个点为右上角、边长为2的整次方幂的Hash值
然后任意一个矩阵都可以用4个矩阵拼起来
但是预处理是O(n^2*log(n))的时间复杂度
所以大的点全部跑了1.09-1.27s不等,全部被判T。然而std最大的点都跑了0.6s+啊!被卡常了( ▼-▼ )
Ⅱ.前缀和版本http://paste.ubuntu.com/18292096/
这个是std的算法。统计二维的前缀和,然后每一维单独乘以一个以幂的级数递增的质数
然后要提取矩阵的时候,前缀和减一减,然后统一次数即可。于是预处理只需要O(n^2)即可
Ⅲ.常规矩阵Hashhttp://paste.ubuntu.com/18292122/
之前两个算法都可以做到随机访问。这个Hash方式不行。
它是把x轴和y轴分开Hash,然后滑动窗口,虽然不能做到O(1)的随机访问,但是遍历的话,还是可以做到O(1)的
总结:三种Hash方式应该都是不错的,但从时间复杂度和代码的优美程度来讲,我以后会选择第二种

另外,Hash都会涉及到判重的问题,一般来讲,大家都是使用set
但这一次lcr给我提供了一个很好的解决方案:sort+unique
理论复杂度一样,但实测效果比set快了3-4倍
有图有真相:matrix_set_versionmatrix_unique_version

贴一份前缀Hash+unique的版本:

#include<iostream>
#include<cstdio>
#include<algorithm>
#define UL unsigned long long 
using namespace std;

const int MAXN = 500+9;
const int N = MAXN*MAXN;
const UL P = 131313131;
const UL Q = 49999;

int n,m,lim; char pat[MAXN];
UL mat[MAXN][MAXN],PP[MAXN*2],QQ[MAXN*2],tmp[N];

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

inline UL GetHash(int x, int y, int L){
	UL ret = 0;
	ret = mat[x][y] + mat[x+L][y+L];
	ret -= mat[x+L][y] + mat[x][y+L];
	return ret*PP[1000-y]*QQ[1000-x];
}

inline void init(){
	m = read(); n = read();
	UL p=P,q; lim = min(n,m);
	for (int j=1;j<=m;j++){
		scanf("%s",pat+1);	
		q = Q;
		for (int i=1;i<=n;i++,q*=Q)
			mat[i][j] = (UL)pat[i]*q*p;
		p *= P;
	}
	for (int i=n;i;i--) for (int j=m;j;j--)
		mat[i][j] += mat[i+1][j]+mat[i][j+1]-mat[i+1][j+1];
	QQ[1] = Q; PP[1] = P;
	for (int i=2;i<=1000;i++) 
		QQ[i] = QQ[i-1]*Q,
		PP[i] = PP[i-1]*P;
}

inline bool judge(int L){
	int cnt = 0;
	for (int i=1;i<=n-L+1;i++) 
		for (int j=1;j<=m-L+1;j++)
			tmp[++cnt] = GetHash(i,j,L);
	sort(tmp+1,tmp+1+cnt);
	int tot = unique(tmp+1,tmp+1+cnt) - tmp - 1;
	return tot != cnt;
}

int main(){
	freopen("matrix.in","r",stdin);
	freopen("matrix.out","w",stdout);
	init();
	int l=1,r=lim,mid,vout=0;
	while (l <= r){
		mid = (l+r)/2;
		if (judge(mid)) l = mid+1, vout = mid;
		else r = mid - 1;
	}
	printf("%d\n",vout);
	return 0;
}