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

· · 题解

一道培养注意力机制的好题，主要是笔者的水平的太低，没法快速想到正解。

先看小样例： 1 3 5 7 9
0 8 240 16128 1451520

发现差不多是 O(n!) 级别的：

1！ 3！ 5！ 7！ 9！
0 6 120 5040 362880

上面除以下面得到：

1 3 5 7 9
0 \frac{4}{3} 2 \frac{16}{5} 4

改一下分母：

1 3 5 7 9
\frac{0}{2} \frac{4}{3} \frac{8}{4} \frac{16}{5} \frac{24}{6}

发现分母为 \frac{n+3}{2}。

而分子可以表示为：

1 3 5 7 9
1^2-1 2^2 3^2-1 4^2 5^2-1

注意到分子在 \frac{n+3}{2} 为奇数时为 \left(\frac{n+1}{2}\right)^2，偶数时为 \left(\frac{n+1}{2}\right)^2-1。或者写为 \left(\frac{n+1}{2}\right)^2-\left(\left(\frac{n+1}{2}\right)\mod 2\right)。

综上所述，答案即为 \frac{\left(\frac{n+1}{2}\right)^2-\left(\left(\frac{n+1}{2}\right)\mod 2\right)}{\frac{n+3}{2}}n!。

线性求逆元和阶乘，O(1) 回答。时间复杂度 O(n+T)。

参考代码：

#include<iostream>
using namespace std;
using ll=long long;
const ll N=1e7;
ll mod;
ll inv[N+10],fac[N+10];
int main(){
    int t;
    cin>>t>>mod;
    fac[0]=1;
    inv[1]=1;
    for(int i=1;i<=N;++i)fac[i]=fac[i-1]*i%mod;
    for(int i=2;i<=N;++i)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    for(;t;--t){
        ll n;
        scanf("%lld",&n);
        printf("%d\n",fac[n]*inv[(n+3)/2]%mod*((n+1)*(n+1)/4%mod-(n+1)/2%2)%mod);
    }
}