[OpenJudge 3066]随机序列
试题描述
Bob喜欢按照如下规则生成随机数：
第一步：令a[0] = S, 当n = 0；
第二步：a[n+1] = (a[n]*A+B)%P；
第三步：如果a[n+1]在之前出现不超过两次，n = n + 1 并且转到第二步。
比如，如果S=4, A=2, B=1并且P=6，那么我们构建的序列是4，3，1，3，1
Bob认为两个随机产生的序列之前应该会有某种关联。所以他想知道这两个随机生成的序列的最长公共子序列。一个序列的子序列是指可以从该序列中删除某些元素（不改变剩余元素顺序）之后得到的序列。
输入
第一行包括一个整数T(T < 15)，表示有多少组测试数据。
每一组测试数据包含两行，每一行都包含四个整数，分别是S, A, B 和 P，用来生成随机序列
0 < S,A,B,P < 200000.
输出
对于每一组测试数据，在一行中输出测试数据的序号以及最长公共子序列。请参照下面的输出样例。
输入示例
输出示例
Case :
Case :
Case :
数据规模及约定
见“输入”
题解
直接做 O(n2) 的 dp 显然是会 T 的，然而我们发现每个数至多出现两次，于是我们可以记下第一个数列中每个数出现的位置，把第二个数列中每个数转化成第一个中该数出现位置的降序排列，例如 a1 = { 4, 1, 3, 1, 3 }，那么其中 4 的位置有 { 1 }，1 的位置有 { 2, 4 }，3 的位置有 { 3, 5 }，那么如果 a2 = { 5, 2, 4, 1, 3, 4 }，它就会被转化成 { 1, 4, 2, 5, 3, 1 } 这个样子。然后不难发现，转化后的数列求最长上升子序列就是答案了，时间复杂度可以做到 O(nlogn)。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <map>
#include <set>
using namespace std; const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
if(Head == Tail) {
int l = fread(buffer, 1, BufferSize, stdin);
Tail = (Head = buffer) + l;
}
return *Head++;
}
int read() {
int x = 0, f = 1; char c = Getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }
return x * f;
} #define maxn 400010
#define oo 2147483647
#define LL long long
int S, A, B, P, n, m, a1[maxn], a2[maxn<<1], pos[maxn][5], cnt[maxn], c2[maxn];
int f[maxn<<1], g[maxn<<1]; int main() {
int T = read(), kase = 0;
while(T--) {
memset(cnt, 0, sizeof(cnt));
memset(c2, 0, sizeof(c2));
S = read(); A = read(); B = read(); P = read();
a1[n = 1] = S; pos[a1[n]][++cnt[a1[n]]] = 1;
for(;;) {
a1[++n] = ((LL)a1[n-1] * A + B) % P;
if(cnt[a1[n]] >= 2){ n--; break; }
pos[a1[n]][++cnt[a1[n]]] = n;
}
// for(int i = 1; i <= n; i++) printf("%d ", a1[i]); putchar('\n');
S = read(); A = read(); B = read(); P = read();
int x = S;
m = 0;
for(int i = cnt[S]; i; i--) a2[++m] = pos[S][i];
for(;;) {
x = ((LL)x * A + B) % P;
if(c2[x] >= 2) break;
c2[x]++;
for(int i = cnt[x]; i; i--) a2[++m] = pos[x][i];
} for(int i = 1; i <= m; i++) g[i] = oo;
g[1] = a2[1];
int ans = 0;
for(int i = 2; i <= m; i++) {
int k = lower_bound(g + 1, g + m + 1, a2[i]) - g;
f[i] = k; ans = max(ans, f[i]);
g[k] = a2[i];
}
printf("Case %d: %d\n", ++kase, ans);
} return 0;
}