题解：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)。代码很短。


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