GMOJ 6809. 【2020.10.29提高组模拟】不难题

题目描述

题解

这题真是恶心到我，交了整整15次才切。

这题的做法类似之前做过的求在一个平面直角坐标系中，不经过特定的点到达终点的方案数。

设一个(f[i])表示连续走了(k)次(i)，且(i)之前的的点都做完了的方案数。

暴力转移是(O(n^5))级别的，所以要优化。

第一个优化，发现固定左端点，右端点每次递增，很好维护，可以优化到(O(n^4))。
第二个优化，利用题目数据随机的条件。因为只有当(y)的每个点都在(x)前面的时候，(f[y])才可以转移到(f[x])，所以可以很容易发现，随着区间右端点(R)的增大，(x)能走到的点越来越少，所以只需要每次记录一下(x)可以走到点，就能大大降低时间复杂度。
但是这样还是会超时，看了LAZA的博客之后，我又发现了另外一种优化方法，可以发现如果(R)每次都从(L)开始枚举，是很慢的。所以我们不妨预处理的时候将(R=L)的情况处理了，直接从(L+1)开始枚举，这样就能过了。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 301
#define mo 1000000007
#define ll long long
#pragma GCC optimize(3)
using namespace std;
int n,k,i,j,l,r,a[N][N],f[N],x,y,p[2][N][N],wp[N][N],xp;
ll fac[N*N],inv[N*N],ans,sum[N][N],sum1[N][N],pl[2][N][N],pl1[2][N][N];
ll mi(ll x,ll n){
	if (n==1) return x;
	ll sum=mi(x*x%mo,n/2);
	if (n%2) sum=sum*x%mo;
	return sum;
}
int main(){
	freopen("nothard.in","r",stdin);
	freopen("nothard.out","w",stdout);
	scanf("%d%d",&k,&n);
	fac[0]=1;
	for (i=1;i<=n*k;i++) fac[i]=fac[i-1]*i%mo;
	inv[n*k]=mi(fac[n*k],mo-2);
	for (i=n*k-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mo;
	inv[0]=1;
	for (i=1;i<=k;i++){
		for (j=1;j<=n;j++) scanf("%d",&a[i][j]),wp[a[i][j]][i]=j;
		a[i][n+1]=n+1;wp[n+1][i]=n+1;
	}
	for (l=1;l<=k;l++){
		xp=0;
		for (i=1;i<=n+1;i++)
			sum[i][l]=wp[i][l]-1,sum1[i][l]=inv[wp[i][l]-1],p[xp][i][0]=0;
		for (i=1;i<=n+1;i++)
			for (j=1;j<=n+1;j++)
				if (wp[j][l]<wp[i][l]){
					p[xp][i][++p[xp][i][0]]=j;
					pl[xp][i][p[xp][i][0]]=wp[i][l]-wp[j][l]-1;
					pl1[xp][i][p[xp][i][0]]=inv[wp[i][l]-wp[j][l]-1];
				}
		for (r=l+1;r<=k;r++){
			xp^=1;
			for (i=1;i<=n+1;i++){
				x=a[l][i];
				sum[x][r]=sum[x][r-1]+wp[x][r]-1;
				sum1[x][r]=sum1[x][r-1]*inv[wp[x][r]-1]%mo;
				f[x]=fac[sum[x][r]]*sum1[x][r]%mo*fac[r-l+1]%mo;
				p[xp][x][0]=0;
				for (j=1;j<=p[xp^1][x][0];j++)
					if (wp[p[xp^1][x][j]][r]<wp[x][r]){
						y=p[xp^1][x][j];
						p[xp][x][++p[xp][x][0]]=y;
						pl[xp][x][p[xp][x][0]]=pl[xp^1][x][j]+wp[x][r]-wp[y][r]-1;
						pl1[xp][x][p[xp][x][0]]=pl1[xp^1][x][j]*inv[wp[x][r]-wp[y][r]-1]%mo;
						f[x]=(f[x]+mo-f[y]*fac[pl[xp][x][p[xp][x][0]]]%mo*pl1[xp][x][p[xp][x][0]]%mo*fac[r-l+1]%mo)%mo;
					}
			}
			ans=(ans+f[n+1]*inv[r-l+1])%mo;
		}
	}
	printf("%lld
",ans);
	return 0;
}