@topcoder - SRM766R1 D1L3@ ShortestMissingSubsequences

@description@
@solution@
@accepted code@
@details@

@description@

给定一个大小为 G 的字符集，并给定一个长度为 N 的字符串 A。

求最短不是 A 的子序列的字符串的长度为 L，以及长度为 L 的不是 A 的子序列的字符串数量 X。

1 <= N <= 2,000,000; 1 <= G <= 10^9。

@solution@

暴力做法？考虑将 A 的所有子序列塞进 trie 里面，则 trie 中出度不为 G 的点后面加字符一定不是 A 的子序列。

注意到这是一个有限状态自动机，可以识别 A 的所有子序列（oi-wiki 上好像把它叫作序列自动机？）。

考虑简化这个自动机。记结点 i 能识别的字符串为以 A[i] 为结尾的，且在 A[1...i-1] 中没有出现的子序列。

假设 i 前面第一个与它相同的位置在 lst[i]，则 lst[i] 之前的连向 i 就会重复，而 [lst[i], i-1] 连向 i 恰好是所有可能的子序列。

注意到这是一个区间的连边形式，我们可以线段树优化连边。

（还有另一种理解方式：第 i 个点的字符 j 转移边，连向 i 之后第一个 j 的出现位置。这个解释可以在 oi-wiki 中看到。）

注意一个结点可以表示多个字符串，而有用的只有这个结点能够表示的最短的字符串。

我们处理出 len[i] 表示以 i 结尾的最短子序列长度，并记 cnt[i] 表示最短子序列的种类数。

连完边后一样看出度是否为 G。

记 oud[i] 表示 i 的出度，则 i 对 len[i] + 1 长度有着 (G - oud[i])*cnt[i] 的贡献。

实际操作并不需要真的连边，只需要用线段树维护上面三种信息。

@accepted code@

#include <unordered_map>

#include <cstdio>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

class ShortestMissingSubsequences{

	private :

		#define MAXN 2000000

		#define MOD 1000000007

		typedef pair<int, int> pii;

		typedef long long ll;

		unordered_map<int, int>mp;

		int A[MAXN + 5], lst[MAXN + 5];

		int len[MAXN + 5], tot[MAXN + 5], cnt[MAXN + 5];

		#define lch (x<<1)

		#define rch (x<<1|1)

		pii tag[4*MAXN + 5]; int nw[4*MAXN + 5];

		pii merge(pii a, pii b) {

			pii c; c.first = min(a.first, b.first);

			if( c.first == a.first ) c.second = (c.second + a.second) % MOD;

			if( c.first == b.first ) c.second = (c.second + b.second) % MOD;

			return c;

		}

		void pushup(int x) {tag[x] = merge(tag[lch], tag[rch]);}

		pii get(int x, int l, int r, int ql, int qr) {

			if( ql <= l && r <= qr ) {

				nw[x]++;

				return tag[x];

			}

			if( ql > r || qr < l )

				return make_pair(MAXN + 5, 0);

			int m = (l + r) >> 1;

			return merge(get(lch, l, m, ql, qr), get(rch, m + 1, r, ql, qr));

		}

		void update(int x, int l, int r, int p) {

			if( l == r ) {

				tag[x] = make_pair(len[p], tot[p]);

				return ;

			}

			int m = (l + r) >> 1;

			if( p <= m ) update(lch, l, m, p);

			else update(rch, m + 1, r, p);

			pushup(x);

		}

		void push(int x, int l, int r, int d) {

			d += nw[x];

			if( l == r ) {

				cnt[l] = d;

				return ;

			}

			int m = (l + r) >> 1;

			push(lch, l, m, d), push(rch, m + 1, r, d);

		}

	public :

		vector<int>count(int G, int N, vector<int>Aprefix) {

			int M = Aprefix.size();

			for(int i=0;i<M;i++) A[i+1] = Aprefix[i];

			ll state = A[M];

			for(int i=M+1;i<=N;i++) {

				state = (state * 1103515245LL + 12345) % (1LL<<31);

				A[i] = state % G;

			}

			for(int i=1;i<=N;i++)

				lst[i] = mp[A[i]], mp[A[i]] = i;

			len[0] = 0, tot[0] = 1, update(1, 0, N, 0);

			for(int i=1;i<=N;i++) {

				pii p = get(1, 0, N, lst[i], i - 1);

				len[i] = p.first + 1, tot[i] = p.second;

				update(1, 0, N, i);

			}

			push(1, 0, N, 0);

			int mn = MAXN + 5;

			for(int i=0;i<=N;i++)

				if( cnt[i] != G )

					mn = min(mn, len[i]);

			vector<int>ans; ans.push_back(mn + 1);

			int x = 0;

			for(int i=0;i<=N;i++)

				if( len[i] == mn )

					x = (x + 1LL*tot[i]*(G - cnt[i])%MOD) % MOD;

			ans.push_back(x);

			return ans;

		}

};

@details@

被小小地卡了一下常。。。

巴特西

@topcoder - SRM766R1 D1L3@ ShortestMissingSubsequences

@description@

@solution@

@accepted code@

@details@

最新文章

热门文章