Loj #6069. 「2017 山东一轮集训 Day4」塔

题目描述

现在有一条 $ [1, l] $ 的数轴，要在上面造 $ n $ 座塔，每座塔的坐标要两两不同，且为整点。

塔有编号，且每座塔都有高度，对于编号为 $ i $ 座塔，其高度为 $ i $。对于一座塔，需要满足它与前面以及后面的塔的距离大于等于自身高度（不存在则没有限制）。问有多少建造方案。答案对 $ m $ 取模。

塔不要求按编号为顺序建造。

输入格式

一行三个整数 $ n, l, m $。

输出格式

输出一个整数，代表答案对 $ m $ 取模的值。

样例

样例输入

3 9 17

样例输出

数据范围与提示

对于 $ 10% $ 的数据，$ n \leq 10; l \leq 25 $；

对于 $ 30% $ 的数据，$ n \leq 20 $；

对于 $ 50% $ 的数据，$ n \leq 50 $；

对于 $ 70% $ 的数据，$ l \leq 105 $；

对于 $ 100% $ 的数据，$ n \leq 100; 1 \leq l \leq 10 ^ 9; 1 \leq m \leq 10 ^ 9 $。

首先我们得到一个排列$P$,设$S=\sum max\{P_{i-1},P_i\}$，$S+1$就是这个排列紧密地排在一起时的长度。还剩下了$l-(S+1)$个格子，我们就将这些格子放在相邻的元素之间，方案数为$\binom{l-S-1+n}{n}$。

所以我们要先求出$S=k$的排列个数。

设$f_{i,j,k}$表示放了前$i$个数，整个排列分为了$j$个联通块，排列的总长度为$k$的方案数。因为我们设从小到大放数，所以如果一个数$i$，它的左侧是空的或者会有另一个数，则不会对$S$有贡献，右侧同理。

转移的时候就考虑第$i$个数与多少个联通块相连（最多两个），就可以知道第$i$个数对$S$的贡献。

接下来考虑处理组合数。因为$n$比较小，所以对于每个$L$,我们只保留$\binom{L}{0..n}$。用矩阵快速幂处理即可。

代码：

#include<bits/stdc++.h>

#define ll long long

#define N 105

using namespace std;

inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}

int n,l;

ll mod;

int f[N][N*N],g[N][N*N];

int per[N*N];

struct matrix {

	int a[105][105];

	void Init() {

		memset(a,0,sizeof(a));

	}

}F,G;

int Mod(int a) {return a<mod?a:a-mod;}

matrix operator *(const matrix &x,const matrix &y) {

	static matrix tem;

	tem.Init();

	for(int i=0;i<=n;i++)

		for(int j=0;j<=n;j++)

			for(int k=0;k<=n;k++)

				tem.a[i][j]=Mod( tem.a[i][j]+1ll*x.a[i][k]*y.a[k][j]%mod);

	return tem;

}

matrix ksm(matrix g,int x) {

	matrix ans;

	ans.Init();

	for(int i=0;i<=n;i++) ans.a[i][i]=1;

	for(;x;x>>=1,g=g*g)

		if(x&1) ans=ans*g;

	return ans;

}

int main() {

	n=Get(),l=Get(),mod=Get();

	int sum=0;

	f[1][0]=1;

	sum=2;

	for(int i=2;i<=n;i++) {

		for(int j=1;j<i;j++) memset(g[j],0,sizeof(g[j]));

		for(int j=1;j<=i;j++) {

			for(int k=0;k<=sum;k++) {

				if(!f[j][k]) continue ;

				g[j+1][k]=Mod(g[j+1][k]+1ll*f[j][k]*(j+1)%mod);

				g[j][k+i]=Mod(g[j][k+i]+1ll*f[j][k]*j*2%mod);

				if(j>1) g[j-1][k+2*i]=Mod(g[j-1][k+2*i]+1ll*f[j][k]*(j-1)%mod);

			}

		}

		memcpy(f,g,sizeof(f));

		sum+=2*i;

	}

	for(int i=0;i<sum;i++) per[i+1]=f[1][i];

	int mx=0;

	for(int i=0;i<sum;i++) if(per[i]) mx=i;

	mx=min(mx,l+n);

	F.a[0][0]=1;

	for(int i=0;i<=n;i++) {

		G.a[i][i]=1;

		if(i) G.a[i-1][i]=1;

	}

	F=F*ksm(G,l-mx+n);

	ll ans=0;

	for(int i=mx;i>=0;i--) {

		(ans+=1ll*per[i]*F.a[0][n])%=mod;

		for(int j=n;j>0;j--) {

			(F.a[0][j]+=F.a[0][j-1])%=mod;

		}

	}

	cout<<ans;

	return 0;

}

巴特西

Loj #6069. 「2017 山东一轮集训 Day4」塔

Loj #6069. 「2017 山东一轮集训 Day4」塔

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示

最新文章

热门文章