自动搬运

查看原文

来自洛谷，原作者为

	•́へ•́╬ Unsuccessful Leaving Something attempt

搬运于2025-08-24 22:48:12，当前版本为作者最后更新于2023-06-22 19:21:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

困难的。看了官方题解。

思路

把操作产生的排列之间的转化关系画成一棵内向树。下图是 $n=3,4$ 的：

可以找到规律：这棵树可以分成 $n$ 个部分，每个部分之间有代价为 $n-1$ 的边相连。

然后官方题解从这里就开始飚式子了。我继续找规律。

下图是 $n=5$ 的图的 $\frac 1 5$。

这 些 是 $n=6$ 的 图 的 $\frac 1 6$。我把它们打印出来找到了规律：

在 $n-2$ 棵大子树中，第 $i$ 棵大子树的前 $i-1$ 棵小子树与前 $i-1$ 棵大子树完全一样，第 $i$ 棵大子树的其余小子树都与第 $i-1$ 棵大子树完全一样。

code

#include<stdio.h>
#define int long long
int n,mod,ans,pfxcnt,nowcnt,pfxans,nowans,fac;
main()
{
	scanf("%lld%lld",&n,&mod);
	if(n==2){putchar('1');return 0;}
	ans=1;pfxcnt=nowcnt=nowans=pfxans=1;
	for(int i=2;i<=n-2;++i)
	{
		nowans=(pfxans+nowans*(n-i)+nowcnt*((n-i+1)*(n-i)/2%mod))%mod;
		nowcnt=(pfxcnt+nowcnt*(n-i)+1)%mod;
		nowans=(nowans+nowcnt*i)%mod;
		pfxcnt=(pfxcnt+nowcnt)%mod;
		pfxans=(pfxans+nowans)%mod;
		ans=(ans+nowans)%mod;
	}
	fac=1;for(int i=2;i<n;fac=fac*i%mod,++i);
	printf("%lld",(ans*n+fac*((n-1ll)*n/2%mod)%mod*(n-1))%mod);
}