题解：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)

。

参考代码：

CPP

#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);
    }
}

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

文章操作

相关推荐

评论

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