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

· · 题解

诶诶，这好像是第一次场切紫诶（？

首先操作一免费，于是两个数字在经过若干次操作一后不同当且仅当奇偶性不同。

于是就变成了只考虑奇偶性的问题。

因此操作二等价于相邻位反转。

我们可以通过操作二将 1 和 0 交换，然后再将相邻的同种数字消灭成另一种数字。

给的是排列，而 n 又是奇数，所以其中奇偶数数量必有一个是奇数。

而奇数个数无法全部消灭成另一个数，所以转化的方向性得到了保证。

接下来考虑计算贡献。

我们假设待消灭数字有 A 个，我们有 B 个已经是目标种类的数字。显然这两个数在得到 n 时就可以计算出来。

如果不考虑这 B 个数，那么剩下的 A 个数显然会选择将 \lceil\frac i 2\rceil 相等的两个 i 放一起消除。

考虑一个 B 造成的贡献，显然只有放在两个成对的 A 之间才会让移动距离多增加 1。

然后你会发现有几种方案使得固定的某个 B 放在满足上述条件的位置是好算的。

如果每个 A 和 B 都相同，这种局面相当于确定下来 A+1 个点后剩下 B-1 个点随意插入。

然后最后还有 A 个数字任意排列与 B-1 个数字任意排列后产生的贡献。

这样就解决了单个 B 的贡献。

假设现在我们知道了 x 作为 B 的贡献，我们需要求同是 B 的 y 的贡献。

根据全排列的定义，显然将每一个排列中 x 和 y 的位置互换得到的排列集合恰好也是全排列。

然后交换以后 x 就能够获得等同于 y 的贡献，而此时所有出现过的排列也依然是全排列，也就是最开始的答案。

那么也就是说每一个 B 的贡献都相同。

所以我们只需要求出一个的答案再乘上 B 就做完了！

千万不要忘记移到相邻位置后消灭还需要一步哇 qwq

于是做完了。

#include<bits/stdc++.h>
#define int long long
#define N 10000000
int mod;
using namespace std;
int qpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}
int A[N+5],inv[N+5];
void solve(){
    int n;
    cin>>n;
    int x=n/2;
    if(x&1)x++;
    cout<<(A[x]*(n-x)%mod*(x/2)%mod*A[n]%mod*inv[x+1]%mod+A[n]*(x/2)%mod)%mod<<'\n';
}
signed main(){
    int t;
    cin>>t>>mod;
    A[0]=1;
    for(int i=1;i<=N;i++)
    A[i]=A[i-1]*i%mod;
    inv[N]=qpow(A[N],mod-2);
    for(int i=N;i;i--)
    inv[i-1]=inv[i]*i%mod;
    while(t--)solve();
    return 0;
}
//「大家，对不起。」
// 正因为周遭没有任何人，她才能坦率地说出口。

//「我最喜欢你们了。」
// 也才能将无法告诉他们本人的话语抛在原地，继续迈步前进。

// 朝向最后。
// 朝向终结。
// 只是一味向前。

upd：补充了关于贡献相同的说明。