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

思路是我自己转化的，式子不是我独立推的。但接下来都会讲。

我们把操作转化为对每个后缀和操作。第

1

种操作会给后缀和数组的某个前缀每个数

+2

，第

2

种操作是在第

1

种的基础上给后面那个数

+1

。

不难发现第

1

种操作不会改变后缀和的奇偶性，而我们最终要把后缀和转化为一个等差数列，同时我们的

2

操作的附加操作不能修改第一个后缀和，也就是说总和的奇偶性是不变的，所以我们要把每个后缀和修改成与总和相同的奇偶性。

问题转化为：对于每个排列，与总和奇偶性不同的后缀和数量的和。现在讨论和为偶数的情况（奇数类似）。

我们再转化一步，就是有奇数个奇数的后缀的个数。也就是对于每个长度为

i

的前缀，求出从

n

个数里面选出奇数个奇数的概率。若暂时不考虑顺序，那么式子如下：

\begin{aligned} \sum_{i=1}^{\lceil \frac{n}{2}\rceil}[i \bmod2=1]\sum_{j=1}^n {j\choose i}{n-j \choose \lceil \frac{n}{2}\rceil-i} \end{aligned}

我们通过范德蒙德卷积转化，得到：

\begin{aligned} &\sum_{i=1}^{\lceil \frac{n}{2}\rceil}[i \bmod2=1]{n+1\choose \lceil \frac{n}{2}\rceil+1}\\ =&\lceil \frac{n}{4}\rceil{n+1\choose \lceil \frac{n}{2}\rceil+1}=\frac{\lceil \frac{n}{4}\rceil}{\lceil \frac{n}{2}\rceil+1}{n+1\choose \lceil \frac{n}{2}\rceil} \end{aligned}

此时我们考虑顺序问题，给答案乘上

{\lceil \frac{n}{2}\rceil}!

和

(n-{\lceil \frac{n}{2}\rceil})!

，答案就转化为：

\begin{aligned} \frac{(n+1)! \lceil \frac{n}{4}\rceil}{\lceil \frac{n}{2}\rceil+1} \end{aligned}

对于和为奇数的情况，我们需要修改的就是每个偶数。那么就相当于每个排列少修改一次，我们求出来之后给答案减去

n!

即可。

时间复杂度

O(n+T\log n)

。代码很短。

CPP

#include<bits/stdc++.h>
#define int long long
#define mp make_pair
#define fi first
#define se second
#define lb lower_bound
#define fr front()
#define pii pair<int,int>
#define v 10000000
using namespace std;

int t,n,k,p,jc[10000005];

int ksm(int a,int n){
    int res=1;
    while(n){
        if(n%2)res=(res*a)%p;
        a=(a*a)%p;n/=2;
    }
    return res;
}

signed main(){
    ios::sync_with_stdio(false);
    cin>>t>>p;jc[0]=1;
    for(int i=1;i<=v+1;i++)jc[i]=jc[i-1]*i%p;
    while(t--){
        cin>>n;
        int k1=ceil(1.0*n/4);
        int k2=ceil(1.0*n/2)+1;
        int ans=jc[n+1]*k1%p*ksm(k2,p-2)%p;
        if((n*(n+1)/2)%2)ans=(ans-jc[n]+p)%p;
        cout<<ans<<"\n";
    }
}

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

文章操作

相关推荐

评论

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