P9419 [POI2021-2022R1] Układanie kart 题解

· · 题解

困难的。看了官方题解。

思路

把操作产生的排列之间的转化关系画成一棵内向树。下图是 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);
}