题解
听说是什么序列自动机？
我们考虑对于每个位置的串，下面拼接相同的字符时，拼接最近的一个，这样可以保证不重不漏
为了实现这个我们需要什么呢，我们需要一个链表，记录一下每个位置的下一个字符会转移到哪里
例如
ABAB
ch[1]['A'] = 3 ch[1]['B'] = 2
听起来挺好建的，具体可以看代码
然后我们记录dp[a][b]是第一个字符串a位置的字符为开头，第二个字符串b位置的字符为开头，公共子序列的个数
可以记忆化搜索，每一次枚举下一个位置拼接上哪个字符
输出方案的话也是一样，枚举下一个位置拼上哪个字符
后五个点需要高精度啊= =
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>
//#define ivorysi
#define pb push_back
#define space putchar(' ')
#define enter putchar('
')
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define mo 974711
#define MAXN 3055
#define RG register
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {putchar('-');x = -x;}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int N,M,MK,ci[205];
char x[MAXN],y[MAXN],ic[205],s[MAXN];
struct segAM {
int head[62],next[MAXN],ch[MAXN][62],tot;
segAM() {
tot = 1;next[1] = 0;
for(int i = 0 ; i <= 60; ++i) head[i] = 1;
}
void Insert(char c) {
++tot;
next[tot] = head[ci[c]];
for(int i = 0 ; i <= 51 ; ++i) {
for(int j = head[i] ; j && !ch[j][ci[c]] ; j = next[j]) {
ch[j][ci[c]] = tot;
}
}
head[ci[c]] = tot;
}
}S1,S2;
const int BASE = 100000000;
const int LEN = 8;
struct Bignum {
vector<int> v;
Bignum operator = (int64 x) {
v.clear();
do {
v.pb(x % BASE);
x /= BASE;
}while(x);
return *this;
}
friend Bignum operator + (const Bignum &a,const Bignum &b) {
Bignum c;c.v.clear();
int p = 0,g = 0;
while(1) {
int x = g;
if(p < a.v.size()) x += a.v[p];
if(p < b.v.size()) x += b.v[p];
++p;
if(!x) break;
c.v.pb(x % BASE);
g = x / BASE;
}
return c;
}
void print() {
int s = v.size() - 1;
printf("%d",v[s]);
--s;
for(int i = s ; i >= 0 ; --i) {
printf("%08d",v[i]);
}
}
}dp[MAXN][MAXN];
bool vis[MAXN][MAXN];
void get(int a,int b) {
if(a == 0 || b == 0) return;
if(vis[a][b]) return;
dp[a][b] = 1;
vis[a][b] = 1;
for(int i = 0 ; i <= 51 ; ++i) {
int ta = S1.ch[a][i],tb = S2.ch[b][i];
get(ta,tb);
dp[a][b] = dp[a][b] + dp[ta][tb];
}
}
void get2(int a,int b,int dep) {
if(a == 0 || b == 0) return;
s[dep] = 0;if(dep != 0) printf("%s
",s);
for(int i = 0 ; i <= 51 ; ++i) {
s[dep] = ic[i];
get2(S1.ch[a][i],S2.ch[b][i],dep + 1);
}
}
void Solve() {
read(N);read(M);
scanf("%s%s",x + 1,y + 1);
read(MK);
for(char i = 'A' ; i <= 'Z' ; ++i)
ci[i] = i - 'A',ic[i - 'A'] = i;
for(char i = 'a' ; i <= 'z' ; ++i)
ci[i] = i - 'a' + 26,ic[i - 'a' + 26] = i;
for(int i = 1 ; i <= N ; ++i) S1.Insert(x[i]);
for(int i = 1 ; i <= M ; ++i) S2.Insert(y[i]);
if(MK == 1) get2(1,1,0);
get(1,1);
dp[1][1].print();enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
return 0;
}
今天写的题解全是FJOI啊（其实还写了2道JOI的水题，太水了不写题解了）
zxg说让我们看看数学相关的集训队论文，然后做做FJ和SC的省选= =
FJ猫锟 SC YJQ
我们都表示毫不理解该省省选题和该省出题人有什么关系，真的不懂中老年人思维啊
但是反正都是要无脑提高刷题量嘛（大雾）
量变能带来质变
……吗？
39天NOI2018打卡