题解：P14352 排序

· · 题解

怎么求一个排列需要几轮才能排完。

把 a_i 看位置 i 竖着叠了 a_i 个 1。然后用 0 补齐顶端。

发现等价于对每行单独做。总轮是每行的轮数取 \max。

把这个排列看作 n 个 01 序列。从下往上枚举每个序列，前一个序列的一个 1 变成 0 得到现在的序列。

排列有序需要的次数等于每个 01 序列，每个 0 离目标位置的距离，的最大值。

所以对于第一个 01 序列，那个 0 可以放到 [1,k+1] 的位置。第 i 个 01 序列，新加入的 0 可以放到 [1,k+i] 中任意一个空位。

当 k+i>n 时就可以在 [1,n] 选择任意一个空位。

所以方案数是：

(\prod_{i=1}^{n-k} k+1)(\prod_{i=n-k+1}^n n-i+1) 
#include<bits/stdc++.h>
#define sf scanf 
#define pf printf 
#define rep(x,y,z) for(int x=y;x<=z;x++) 
#define per(x,y,z) for(int x=y;x>=z;x--) 
using namespace std;
typedef long long ll;
namespace wing_heart {
    constexpr int K=2e7,mod=998244353;
    int ksm(int a,ll b) {
        int s=1;
        while(b) {
            if(b&1) s=1ll*s*a%mod;
            a=1ll*a*a%mod;
            b>>=1;
        }
        return s;
    }
    ll n;
    int k;
    int ans;
    void main() {
        sf("%lld%d",&n,&k);
        k=min(1ll*k,n);
        ans = ksm(k+1,n-k);
        for(ll x=n-k+1;x<=n;x++) ans = 1ll*ans*(n-x+1)%mod;
        pf("%d\n",ans);
    }
}
int main() {
    wing_heart :: main();
}