edward_mj

【Link】

求串A和串B偏序匹配的所有位置。偏序匹配就是保持大小关系的离散化后两个串一模一样。\[1 \leq |A|, |B| \leq 10^5, 1 \leq A_i, B_i \leq 25 \]

昨天网络赛的B题，我们当时随便弄了个$$25*(|A| + |B|)$$的hash就过了，后来在Vani那听说有n lg k(k为字符集大小)的做法，想了一下总算明白了。记录一下。
其实满足以下两条性质的匹配关系都能KMP：

1. 匹配的前缀性质。也就是说：若$$A_{1..n}$$和$$B_{1..n}$$匹配，那么对于任意$$i=1..n$$，有$$A_{1..i}$$和$$B_{1..i}$$匹配。
2. 偏序匹配符合传递性。假设用\(\approx\)表示两个串符合偏序匹配，那么$$A \approx B , B \approx C \Rightarrow A \approx C$$

既然能KMP了，关键就在于判断他们什么时候能往后面加一个字符。
考虑两个相同长度的串$$A_{1..n}, B_{1..n}$$他们已经能够构成偏序匹配，那么假设现在新增了一个元素，构成了$$A_{1..n+1}, B_{1..n+1}$$，那么他们同样能构成偏序匹配的充要条件是什么呢？
仔细想想不难YY到：
\(count(A_i < A_{n+1}) = count(B_i < B_{n + 1}), i = 1..n\) \(count(A_i = A_{n + 1}) = count(B_i = B_{n + 1}), i = 1..n\) \(count(A_i > A_{n + 1}) = count(B_i > B_{n + 1}), i = 1..n\)
因为n是固定的，所以只关注前两个条件即可。
然后这东西可以用树状数组维护。
KMP维护的实际是两个指针j和i，表示$$A_{j..i}$$ 和 $$B_{1..i-j+1}$$匹配，本质上i和j都是递增的，所以i加的时候把a[i]放进BIT，j加的时候扔出树状数组即可。
而模式串因为只和前缀比较，所以可以预处理出low和eq数组

时间复杂度 $$O(n \log_2 k)$$
空间复杂度 $$O(n)$$

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define foreach(it,v) for (__typeof((v).end()) it = (v).begin(); it != (v).end(); it++)
typedef pair <int, int> PII;
typedef long long ll;
const int N = 100005;
int n, m, p;
int a[N], b[N];
int Tr[30];
int low[N], eq[N];
int Next[N];
bool mat[N];

int get(int i) {
	int res = 0;
	for (; i; i -= i & -i) res += Tr[i];
	return res;
}

void add(int i, int x) {
	for (; i < = p; i += i & -i) Tr[i] += x;
}

void init() {
	fill(Tr, Tr + p + 1, 0);
	low[0] = eq[0] = 0;
	for (int i = 1; i <= m; i++) {
		low[i] = get(b[i] - 1);
		eq[i] = get(b[i]) - low[i];
		add(b[i], 1);
	}
}

int last;

bool ok(int *a, int lim, int x, int j) {
	while (last < lim) add(a[last++], -1);
	int l = get(x - 1), e = get(x) - l;
	return l == low[j] && e == eq[j];
}

int f[N];

void kmp() {
	fill(Tr, Tr + p + 1, 0);
	fill(mat, mat + n + 1, 0);
	int j = 0;
	Next[1] = 0;
	last = 1;
	add(b[1], 1);
	for (int i = 2; i <= m; i++) {
		while (j && !ok(b, i - j, b[i], j + 1)) {
			j = Next[j];
		}
		if (j == 0 || ok(b, i - j, b[i], j + 1)) j++;
		Next[i] = j;
		add(b[i], 1);
	}
	fill(Tr, Tr + p + 1, 0);
	j = 0;
	last = 1;
	for (int i = 1; i <= n; i++) {
		while (j && !ok(a, i - j, a[i], j + 1)) {
			j = Next[j];
		}
		if (j == 0 || ok(a, i - j, a[i], j + 1)) {
			j++;
		}
		if (j == m) {
			mat[i] = 1;
			j = Next[j];
		}
		add(a[i], 1);
	}
}

int main() {
	while (scanf("%d%d%d", &n, &m, &p) != EOF) {
		for (int i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
		}
		for (int i = 1; i <= m; i++) {
			scanf("%d", &b[i]);
		}
		init();
		kmp();
		fill(f, f + n + 1, 0);
		for (int i = 1; i <= n; i++) {
			f[i] = f[i - 1];
			if (i - m >= 0) f[i] = max(f[i], f[i - m] + mat[i]);
		}
		printf("%d\n", f[n]);
	}
}

传送门(Problem E)

题目描述得很麻烦，但是实际上是给定一个正整数矩阵$$A_{n*n}$$，问是否存在两个向量$$X_{1..n}$$, $$B_{1..n}$$使得\( A*X^T = B^T \) 并且B向量的元素全是整数，而X向量的元素不全是整数。$$1 \leq n \leq 100$$, $$\vert A_{ij} \vert \leq 100$$

• 如果A不满秩，那么显然存在。
• 如果A满秩，有两种思路
  1. 求A的逆矩阵，看矩阵里有没有非实数，如果有，那么存在这两个向量，否则不存在。具体原因是：$$A*X^T = B^T$$ –> $$X^T = A^{-1}B^T$$。而B里必须是整数，如果A的逆阵也全是整数的话，X只能取整数。但是这个方法需要判断一个逆阵里是否全是整数，而高斯消元的过程中，元素的增长总是指数级的，很容易构造到数据使得精度不够。除非使用Java的BigInteger用分数表示，否则真的是非常繁杂。
  2. 根据cramer法则上面提到的线性方程组的第i组解为\[\frac{det(A_i)}{det(A)}\]其中$$det(A_i)$$表示的是将A矩阵的第i列换成$$B^T$$以后的列向量。由B向量的任意性，这个$$det(A_i)$$可以取任意的整数，这样如果$$det(A)$$不是1或者-1的话，必然可以使得某一个$$X_i$$不是整数。所以归根到底，只要判断$$det(A)$$是不是1或者-1就行了。当然这个即使是实数运算，也比方法1要好得多，但是还是不够靠谱。A的元素是整数，行列式也肯定是整数，那么可以选取若干个素数，求出行列式对这些素数取模以后是不是1或-1，如果验证了好几个素数以后结果还是一致，那么就是正确的。如果担心正确性，可以使取的素数之积达到$$100^{100}$$，这样值域和定义域的大小一致，基本就不会出错了。

#include 
#include 
#include 
#include 
using namespace std;
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
const int N = 105;
int n;
int a[N][N], b[N][N];

int inverse(ll a, int Mod) {
	ll res = 1;
	for (int b = Mod - 2; b; b >>= 1) {
		if (b & 1) res = res * a % Mod;
		a = a * a % Mod;
	}
	return res;
}

bool ok(int Mod) {
	rep (i, n) rep (j, n) b[i][j] = (a[i][j] % Mod + Mod) % Mod;
	ll det = 1;
	rep (i, n) {
		for (int j = i + 1; j < n && !b[i][i]; j++) {
			if (b[j][i]) {
				for (int k = i; k < n; k++)
					swap(b[i][k], b[j][k]);
				det = (-det + Mod) % Mod;
				break;
			}
		}
		if (!b[i][i]) return 0;
		det = (det * b[i][i] % Mod + Mod) % Mod;
		ll inv = inverse(b[i][i], Mod);
		for (int j = i + 1; j < n; j++) {
			if (b[j][i]) {
				ll mul = inv * b[j][i] % Mod;
				for (int k = i; k < n; k++) {
					b[j][k] = ((b[j][k] - mul * b[i][k]) % Mod + Mod) % Mod;
				}
			}
		}
	}
	return (det == 1) || (det == Mod - 1);
}

int main() {
	scanf("%d", &n);
	rep (i, n) rep (j, n) scanf("%d", &a[i][j]);
	if (ok(1000000007) && ok(1000000009) && ok(1000003)) {
		puts("Death");
	} else {
		puts("Power of magic saves lives");
	}
}