2020ICPC·小米邀请赛第二场 G-Shift and Reverse

https://ac.nowcoder.com/acm/contest/7502/G

#### 题目大意：
给定一个长度为$n$数组，每一次可以进行如下操作：
1、将数组划分为前后两段
2、将这两段分别翻转
问最后可能得到多少种数组？
多组数据
$\Sigma n\leq 2\times 10^6$

#### 题解：
考虑相邻两次操作，例如：
ABCDEFGHIJK
$\to$CBA KJIHGFED
$\to$HIJK ABC DEFG
$\to$HIJKABCDEFG
发现相邻两次操作等价于将原串做一个循环
再考虑一次操作
ABCDEFGHIJK
$\to$CBA KJIHGFED
发现一次操作等价于反串后做循环

那么我们证明了所有的可操作出的数组就是正串和反串所有循环串的串集合！

于是哈希将正反串的所有循环串扔set就完了，用一个双哈希，非常简单
复杂度为$n log n$

```
#include<bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 5;
const int base = 19260817;
const int mod = 1e9 + 7;
const int mod2 = 1e9 + 9;
int hsh[maxn], hsh2[maxn], nt[maxn], a[maxn], ans;
int inv_base[maxn], pow_base[maxn], n;
int inv_base2[maxn], pow_base2[maxn];
typedef pair<int, int> pii;
set<pii > st;
int mul(int a, int b) {
	return 1ll * a * b % mod;
}
int mul2(int a, int b) {
	return 1ll * a * b % mod2;
}
int dec(int a, int b) {
	return a - b < 0 ? a - b + mod : a - b;
}
int dec2(int a, int b) {
	return a - b < 0 ? a - b + mod2 : a - b;
}
int add(int a, int b) {
	return a + b >= mod ? a + b - mod : a + b;
}
int add2(int a, int b) {
	return a + b >= mod2 ? a + b - mod2 : a + b;
}
int fpow(int x, int a) {
	int ans = 1;
	while(a) {
		if(a & 1) ans = mul(ans, x);
		a>>= 1, x = mul(x, x);
	}
	return ans;
}
int fpow2(int x, int a) {
	int ans = 1;
	while(a) {
		if(a & 1) ans = mul2(ans, x);
		a >>= 1, x = mul2(x, x);
	}
	return ans;
}

pii Qhsh(int l, int r) {
	return make_pair(mul(dec(hsh[r], hsh[l - 1]), inv_base[l - 1]),
					mul2(dec2(hsh2[r], hsh2[l - 1]), inv_base2[l - 1]));
}
void work() {
	int _2n = n << 1;
	for(int i = 1; i <= n; ++i)
		a[i + n] = a[i];
	for(int i = 1; i <= _2n; ++i) {
		hsh[i] = add(hsh[i - 1], mul(pow_base[i - 1], a[i]));
		hsh2[i] = add2(hsh2[i - 1], mul2(pow_base2[i - 1], a[i]));
	}
	for(int i = 1; i <= n; ++i) {
		st.insert(Qhsh(i, i + n - 1));
		//cerr << "#" << i << " " << i + n - 1 << "#" << Qhsh(i, i + n - 1) << endl;
	}
}

int main() {
	while(~scanf("%d", &n)) {
		st.clear();
		int ibase = fpow(base, mod - 2);
		int ibase2 = fpow2(base, mod2 - 2);
		pow_base2[0] = inv_base2[0] =
		pow_base[0] = inv_base[0] = 1; 
		for(int i = 1; i <= n * 2; ++i) {
			inv_base[i] = mul(inv_base[i - 1], ibase);
			pow_base[i] = mul(pow_base[i - 1], base);
			inv_base2[i] = mul2(inv_base2[i - 1], ibase2);
			pow_base2[i] = mul2(pow_base2[i - 1], base);
		}
		for(int i = 1; i <= n; ++i)
			scanf("%d", &a[i]);
		work();
		reverse(a + 1, a + n + 1);
		work();
		printf("%d\n", st.size());
	}
	return 0;
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链