题解：CF1091D New Year and the Permutation Concatenation

zxh_qwq · 2026-05-14 17:39:00 · 题解

CF1091D 题解

思路

不难发现，如果相邻两个有一个长度为 k 的公共前缀，那么答案会多 k。

我们枚举每种长度的前缀。发现长度为 k 的前缀种类为 \dfrac{n!}{(n-k)!}。

由于按照字典序排序，所以相同前缀一定连续。所以连续相同的长度至少为 k 的前缀共有 (n!-1)-\big(\dfrac{n!}{(n-k)!}-1\big) = n!-\dfrac{n!}{(n-k)!} 个。

我们枚举 k 即可。由于长度至少为 k 的包含了长度至少为 k-1 的，因此只需对每一种答案加上其个数即可。

答案为 n! + \sum_{k=1}^{n} n!-\dfrac{n!}{(n-k)!}，其中前面的 n! 为初始答案总数。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
int fac(int n){
    int mul=1;
    for(int i=1;i<=n;i++)mul=mul*i%mod;
    return mul;
}
main(){
    int n;
    cin>>n;
    int k=fac(n);
    int ans=k,mul=1;
    for(int i=n;i>=1;i--){
        mul*=i;
        mul%=mod; 
        ans+=k-mul;
        ans%=mod;
        ans+=mod;
        ans%=mod;
    }
    cout<<ans;
}