CF1439D INOI Final Contests 题解

Codeforces
Luogu

Description.

有 \(m\) 个人,轮流占位置,第 \(i\) 个人出现在 \(a_i(\in[1,n])\) 并往 左/右 方向移动,占领第一个没有人的位置。
一个方案合法,当且仅当没有一个人它没有位置。
一个方案的权值定义为每个人到它目标位置的距离和。
问所有方案的权值和。

Solution

方案数参考
考虑设计一个 \(dp_{i,j}\) 表示 \(j\) 个人坐到 \(i\) 个座位的答案。(\(g_{i,j}\) 表示方案数


如果 \(i=j\),那直接枚举最后一个人坐到的位置 \(k\) 转移。
首先总方案数是 \(g_{k-1,k-1}\cdot g_{i-k,i-k}\cdot \dbinom{i-1}{k-1}\),最后那个是隔板。
最后一个人的贡献就是 \(\sum_{x=1}^{k-1}x+\sum_{x=1}^{i-k}x\) 即为枚举第 \(i\) 个人目标位置。
然后前面的继承贡献就是 \((f_{k-1,k-1}\cdot g_{i-k,i-k}+f_{i-k,i-k}\cdot g_{k-1,k-1})\cdot \dbinom{i-1}{k-1}\cdot(i+1)\)。
\(i+1\) 表示除了最后一个人插入位置有 \(2\) 个方向,其他都只有一个方向。


如果 \(i\ne j\),那直接枚举最后一段都坐满的长度 \(k\)。
如果 \(k=0\),贡献就是 \(f_{i-1,j}\)。
否则贡献是 \((f_{i-k-1,j-k}\cdot g_{k,k}+f_{k,k}\cdot g_{i-k-1,j-k})\cdot\dbinom{j}{k}\)

Coding.

点击查看 /no 代码
//是啊,你就是那只鬼了,所以被你碰到以后,就轮到我变成鬼了{{{
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
	x=0;char c=getchar(),f=0;
	for(;c<48||c>57;c=getchar()) if(!(c^45)) f=1;
	for(;c>=48&&c<=57;c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	f?x=-x:x;
}
template<typename T,typename...L>inline void read(T &x,L&...l) {read(x),read(l...);}//}}}
const int N=505;int n,m,P,F[N][N],G[N][N];
int fc[N],fi[N],iv[N];//dbinit{{{
inline int ksm(int x,int q=P-2) {int r=1;for(;q;q>>=1,x=1ll*x*x%P) if(q&1) r=1ll*r*x%P;return r;}
inline void dbinit(int n=N-1)
{
	fc[0]=1;for(int i=1;i<=n;i++) fc[i]=1ll*fc[i-1]*i%P;
	iv[1]=1;for(int i=2;i<=n;i++) iv[i]=1ll*iv[P%i]*(P-P/i)%P;
	fi[0]=1;for(int i=1;i<=n;i++) fi[i]=1ll*fi[i-1]*iv[i]%P;
}
inline int C(int n,int m) {return n<0||m<0||n<m?0:1ll*fc[n]*fi[m]%P*fi[n-m]%P;}//}}}
inline int gtg(int n,int m) {return 2ll*(n+1-m)*ksm((n+1)<<1,m-1)%P;}//方案数
inline int S(int x) {return 1ll*x*(x+1)/2%P;}
int main()
{
	read(n,m,P),dbinit();for(int i=0;i<=n;i++) G[i][0]=1;
	for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) G[i][j]=gtg(i,j);
	for(int i=1;i<=n;i++)
	{
		int &rs=F[i][i];rs=0;for(int k=1;k<=i;k++)
		{
			rs=(rs+1ll*G[k-1][k-1]*G[i-k][i-k]%P*C(i-1,k-1)%P*(S(k-1)+S(i-k)))%P;
			rs=(rs+(1ll*F[k-1][k-1]*G[i-k][i-k]+1ll*G[k-1][k-1]*F[i-k][i-k])%P*(i+1)%P*C(i-1,k-1))%P;
		}
	}
	for(int i=1;i<=n;i++) for(int j=1;j<i;j++)
	{
		int &rs=F[i][j];rs=F[i-1][j];for(int k=1;k<=j;k++)
			rs=(rs+(1ll*F[i-k-1][j-k]*G[k][k]+1ll*F[k][k]*G[i-k-1][j-k])%P*C(j,k))%P;
	}
	return printf("%d\n",F[n][m]),0;
}
上一篇:神经网络反向传播算法公式推导


下一篇:python 写文件,utf-8问题