专栏文章

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

ffish_love_cat
P14321题解参与者 5已保存评论 6

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
6 条
当前快照
1 份
快照标识符
@minhq2m0
此快照首次捕获于
2025/12/02 02:36
3 个月前
此快照最后确认于
2025/12/02 02:36
3 个月前
查看原文
诶诶，这好像是第一次场切紫诶（？
首先操作一免费，于是两个数字在经过若干次操作一后不同当且仅当奇偶性不同。
于是就变成了只考虑奇偶性的问题。
因此操作二等价于相邻位反转。
我们可以通过操作二将 11 和 00 交换，然后再将相邻的同种数字消灭成另一种数字。
给的是排列，而 nn 又是奇数，所以其中奇偶数数量必有一个是奇数。
而奇数个数无法全部消灭成另一个数，所以转化的方向性得到了保证。
接下来考虑计算贡献。
我们假设待消灭数字有 AA 个，我们有 BB 个已经是目标种类的数字。显然这两个数在得到 nn 时就可以计算出来。
如果不考虑这 BB 个数，那么剩下的 AA 个数显然会选择将 ⌈i2⌉\lceil\frac i 2\rceil 相等的两个 ii 放一起消除。
考虑一个 BB 造成的贡献，显然只有放在两个成对的 AA 之间才会让移动距离多增加 11。
然后你会发现有几种方案使得固定的某个 BB 放在满足上述条件的位置是好算的。
如果每个 AA 和 BB 都相同，这种局面相当于确定下来 A+1A+1 个点后剩下 B−1B-1 个点随意插入。
然后最后还有 AA 个数字任意排列与 B−1B-1 个数字任意排列后产生的贡献。
这样就解决了单个 BB 的贡献。
假设现在我们知道了 xx 作为 BB 的贡献，我们需要求同是 BB 的 yy 的贡献。
根据全排列的定义，显然将每一个排列中 xx 和 yy 的位置互换得到的排列集合恰好也是全排列。
然后交换以后 xx 就能够获得等同于 yy 的贡献，而此时所有出现过的排列也依然是全排列，也就是最开始的答案。
那么也就是说每一个 BB 的贡献都相同。
所以我们只需要求出一个的答案再乘上 BB 就做完了！
千万不要忘记移到相邻位置后消灭还需要一步哇 qwq
于是做完了。
CPP
#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：补充了关于贡献相同的说明。

评论

共 6 条评论，欢迎与作者交流。

正在加载评论...