P4609题解

P4609 [FJOI2016] 建筑师

外训听完组合数学后题单里的，但觉得

dp

能过，写完真过了。结果一看提交记录，荣获最劣解。再一看题解，怎么都是斯特林数，蒟蒻不会，于是写篇题解

首先，由于要求前后缀最大值的个数，所以我们考虑将数字从大到小插入

记

dp_{i,j,k}

为已经放了前

i

大的数，前后缀最大值分别为

j,k

的答案。

考虑将下一个数，即当前最大值插入对答案的影响。若放在两边，答案不变，前后缀最大值长度增加。若插在中间，由于已插入的数都比当前数大，不会对前后缀最大值产生影响，所以可以随便插，答案乘上

i-2

dp_{i,j,k}=dp_{i-1,j-1,k}+dp_{i-1,j,k-1}+(i-2)\times dp_{i-1,j,k}

初值为

dp_{1,1,1}=1

复杂度

O(nAB)

最大约

5\times 10^8

但常数小，可以通过

但当你兴冲冲写完一交，满屏的

MLE

发现空间也是

O(nAB)

的，所以考虑将第一维滚掉

所以我们先将询问离线，按照

n

从小到大排序，然后一边跑

dp

，一边记录答案

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,M=1e9+7;
int n,A,B,dp[2][110][110],ans[N];
struct que{
	int n,a,b,id;
}q[N];
bool cmp(que x,que y){return x.n<y.n;}
signed main(){
	int T;
	cin>>T;
	for(int i=1;i<=T;i++){
		cin>>q[i].n>>q[i].a>>q[i].b;
		q[i].id=i;
	}
	sort(q+1,q+T+1,cmp);
	int l=1;
	while(q[l].n==1 and l<=T){ans[q[l].id]=((q[l].a==1)and(q[l].b==1));l++;}
	dp[0][1][2]=dp[0][2][1]=1;
	while(q[l].n==2 and l<=T){ans[q[l].id]=dp[0][q[l].a][q[l].b];l++;}
	for(int i=3;i<=q[T].n;i++){
		for(int j=1;j<=min(i,100);j++){
			for(int k=1;k<=min(i,100);k++){
				dp[i&1][j][k]=(dp[i&1^1][j-1][k]+dp[i&1^1][j][k-1]+1ll*dp[i&1^1][j][k]*(i-2))%M;	
			}
		}
		while(q[l].n==i and l<=T){ans[q[l].id]=dp[i&1][q[l].a][q[l].b];l++;}	
	}	
	for(int i=1;i<=T;i++)cout<<ans[i]<<'\n';
	return 0;
}

注意

n

只有

5\times 10^4

，但

T

有

2\times 10^5

，不要开小数组

文章操作

P4609 [FJOI2016] 建筑师

相关推荐

评论

P4609题解