FJOI2016———PAM、斯特林数

发表于

%%%Sparrow

T1:PAM (PWJ AutoMaton)

T1就是求两个字符串有多少个相同子序列传送門

DP：$f[i][j]=(\sum f[u][k]) +1\ u,k为i,j扩展出的子序列$

提到一个新东西，pwj发明的 序列自动机pam

原理很简单，当前位置能扩展出的子序列，取决于后面每个字母第一次出现位置。

自动机的点就是线性的，转移乘上$\alpha$

也就是每个点表示位置，向后面每个字母第一次出现位置连边

代码（map超好实现）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<stdio.h>
#include<algorithm>
#include<map>
using namespace std;
const int N=3005;

struct BigInt{
	const static int M=100000000;
	int len,*d;
	void Init(){
		d=new int[20];
		len=1;
		for(int i=0;i<20;i++)d[i]=0;
	}
	void operator += (const BigInt& s){
		len=max(len,s.len);
		for(int i=0;i<len;i++){
			d[i]+=s.d[i];
			d[i+1]+=d[i]/M;
			d[i]%=M;
		}
		if(d[len])len++;
	}
	void Print(){
		printf("%d",d[len-1]);
		for(int i=len-2;i>=0;i--)
			printf("%08d",d[i]);
	}
}f[N][N];
bool vis[N][N];
map<char,int>Last,Pam[N],Pbm[N];
typedef map<char,int>::iterator mc;
void DP(int i,int j){
	if(vis[i][j])return;
	f[i][j].Init();
	f[i][j].d[0]=1,vis[i][j]=1;
	for(mc it=Pam[i].begin();it!=Pam[i].end();it++)
		if(Pbm[j].count(it->first)){
			DP(it->second,Pbm[j][it->first]);
			f[i][j]+=f[it->second][Pbm[j][it->first]];
		}
}
int n,m,opt;
char A[N],B[N],Buf[N];
void Print(int i,int j,int len){
	Buf[len]=0;
	puts(Buf);
	for(mc it=Pam[i].begin();it!=Pam[i].end();it++)
		if(Pbm[j].count(it->first)){
			Buf[len]=it->first;
			Print(it->second,Pbm[j][it->first],len+1);
		}
}
int main(){
	scanf("%d%d%s%s%d",&n,&m,A+1,B+1,&opt);
	Last.clear();
	for(int i=n;i>=0;i--){
		Pam[i]=Last;
		Last[A[i]]=i;
	}
	Last.clear();
	for(int i=m;i>=0;i--){
		Pbm[i]=Last;
		Last[B[i]]=i;
	}
	if(opt)Print(0,0,0);
	DP(0,0);
	f[0][0].Print();
}

T2:Stirling 斯特林数

原题解在此

把最高的固定，左边A个，右边B个

假设这些能看到的建筑固定，对于每个这样的建筑，它与下一个建筑中的建筑可以任意组合

把每个建筑和它右边这些看做一个大小为k的集合，每个集合有$(k-1)!$种排列

那么它就是一个圆排列，根据题意，我们需要A+B-2个这样的圆排列，根据第一类斯特林数的定义，这样的圆排列有$stirling(n-1.A+B-2)$ 种，我们需要把这些圆排列的A-1个放在左边，有$C(A+B-2,A-1)$种

于是$Ans=stirling(n-1,A+B-2)*C(A+B-2,A-1)$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll Mod=1e9+7;
const int N=50005;

int T;
ll n,A,B,f[N];
ll s[N][205],C[205][205];
void Stirling(){
	s[0][0]=1;
	for(int i=1;i<=50000;i++)
		for(int j=1;j<=200&&j<=i;j++)
			s[i][j]=(s[i-1][j-1]+s[i-1][j]*(i-1)%Mod)%Mod;
}
void Combination(){
	for(int i=0;i<=200;i++)C[i][0]=1;
	for(int i=1;i<=200;i++)
		for(int j=1;j<=i;j++)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%Mod;
}
int main(){
    int i,j,k;
    scanf("%d",&T);
	Stirling();
	Combination();
    while(T--){
        scanf("%lld%lld%lld",&n,&A,&B);
        printf("%lld\n",s[n-1][A+B-2]*C[A+B-2][A-1]%Mod);
    }
}

T3 主席树

一看就想到了主席树做法，结果写错了。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<stdio.h>
#include<algorithm>
using namespace std;
const int N=100005,M=N<<4;

int n,m,a[N];
int tot,Hash[N];
int Totn,Root[N],Son[M][2],Sum[M];
void Build(int &p,int l,int r){
    p=++Totn;
    if(l<r){
         int mid=l+r>>1;
         Build(Son[p][0],l,mid);
         Build(Son[p][1],mid+1,r);
    }
}
int Copy(int p){
    int x=++Totn;
    Son[x][1]=Son[p][1];
    Son[x][0]=Son[p][0];
    Sum[x]=Sum[p];
    return x;
}
int Insert(int p,int l,int r,int k,int d){
    int rt=Copy(p);
	Sum[rt]+=d;
    if(l==r)return rt;
    int mid=l+r>>1;
    if(k<=mid)Son[rt][0]=Insert(Son[rt][0],l,mid,k,d);
    else Son[rt][1]=Insert(Son[rt][1],mid+1,r,k,d);
    return rt;
}
int Query(int p1,int p2,int l,int r,int k){
	if(l==r)return Sum[p2]-Sum[p1];
	int mid=l+r>>1,rt=0;
	if(k>mid)rt=Sum[Son[p2][0]]-Sum[Son[p1][0]]+Query(Son[p1][1],Son[p2][1],mid+1,r,k);
	else rt=Query(Son[p1][0],Son[p2][0],l,mid,k);
	return rt;
}
int main(){
    int i,j,k,t;
    int x,y,ans;
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%d",&a[i]),Hash[i]=a[i];
    sort(Hash+1,Hash+1+n);
    tot=unique(Hash+1,Hash+1+n)-Hash-1;
    Build(Root[0],1,tot);
    for(i=1;i<=n;i++)
      Root[i]=Insert(Root[i-1],1,tot,lower_bound(Hash+1,Hash+1+tot,a[i])-Hash,a[i]);
    scanf("%d",&m);
    while(m--){
        scanf("%d%d",&x,&y);
        ans=1;
        while(1){
			t=Query(Root[x-1],Root[y],1,tot,upper_bound(Hash+1,Hash+1+tot,ans)-Hash-1);
			if(t<ans)break;
			ans=t+1;
		}
        printf("%d\n",ans);
    }
}