题解：P14321 「ALFR Round 11」D Adjacent Lifting, Fewest Rounds

zzy2009hsy · 2025-10-26 19:51:41 · 题解

（一个找规律的做法，实战请勿模仿……）

题意：

题目中已经讲的很清楚了，这里不再赘述。

题目链接。

思路：

带大家重现一下我的考场思路：

首先，对于这种全排列的问题，我们感性的想一下，就觉得 ans 一定与 n! 有关。所以，我先将样例中前五个对应的 ans 分别除以 n!，得到 0、\frac{4}{3}、2、\frac{16}{5}、4（最后一个明显经过了取模，对找规律没有用，因此暂时舍弃）。

再将序号也一起标出来（这里为了方便，序号使用的是 \frac{n+1}{2} 而不是 n）：

这时候，我发现 2\times2=\frac{4}{3}\times3，且 4\times4=\frac{16}{5}\times5，于是脑海中涌现了一个大胆的想法：

当 n\bmod4=1 时，ans=\lfloor\frac{n}{2}\rfloor\times n!。

当 n\bmod4=3 时，设 m=\frac{n+1}{2}，则 ans=\frac{m^2}{m+1}\times n!。

（然后写了一段代码，测了样例发现过了，提交一看居然 ac 了……）

正确性：

题是切了，可这个规律的正确性如何证明呢？

由于本人太菜，而几个 ai 都证不出来，因此这个问题就留给各位大佬们，如果有可以证明的大佬可以私信联系我，万分感谢！

代码实现：

#include<bits/stdc++.h>
#define int long long//注意开long long
using namespace std;
int jc[10000005];
int qp(int x,int y,int mod)
{
    int sum=1;
    while(y)
    {
        if(y&1)
        {
            sum*=x;
            sum%=mod;
        }
        x*=x;
        x%=mod;
        y>>=1;
    }
    return sum;
}//由于题目保证模数为质数，因此这里采用费马小定理求逆元
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);//输入输出优化
    int t,mod;
    cin>>t>>mod;
    jc[0]=1;
    for(int i=1;i<=10000000;i++)
        jc[i]=(jc[i-1]*i%mod);//预处理阶乘值
    while(t--)
    {
        int n;
        cin>>n;
        int sum;
        if(n%4==1)
            sum=n/2;
        else
        {
            int m=(n+1)/2+1;
            int num=(m-1)*(m-1)%mod;
            sum=num*qp(m,mod-2,mod)%mod;
        }//分类讨论
        int ans=jc[n]*sum%mod;
        cout<<ans<<'\n';
    }
    return 0;
}

写在最后：

说实话，能场切这道题完全是我运气好。连代码的正确性都证不出来，说明根本没有掌握题目所考察的知识点，切了也等于白切。

希望大家在刷题时不要连猜带蒙地去找规律，而是真正弄懂每一道题目，这样才能对自己的能力提升带来帮助。