题解：CF1091DNew Year and the Permutation Concatenation

· · 题解

好题

题目传送门

很明显可以把答案拆成两部分计算

第一部分很明显，每个排列都满足排列，即为 !n

那第二部分就是两个排列的部分拼一块儿，我们枚举 i 表示前半部分有i个数，要选数，所以有 C_{n}^{i} ，数字要排列，所以乘上 !i (其实就是 A_{n}^{i} )，前面的数已经确定，再乘排列 !(n-i)

挺有道理，但没结束

我们拿 n=3 的第二部分来举例，当 i=1 时前半部分为：23,13,12 ,注意到不会有 32 ,31, 21，因为他们要搭配的数，在自己的排列中正好最后一次出现在最前面，前面数的全排列少了一半，故将 !(n-i) 减一

答案：

ans=!n+\sum_{i = 1}^{n-1} A_{n}^{i}*!(n-i)

别忘取模。

Code: 
#include<bits/stdc++.h>
#define int long long
#define lowbit(x) x&-x
#define P(x,y) make_pair(x,y)
#define PII pair<int,int>
#define x first
#define y second
using namespace std;
const int mod=998244353;
double eps=1e-6;
const int N=1e6+10;
int jie[N];

int n;
int qpow(int a,int b)
{
    int res=1;
    for(;b;b>>=1)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
    }
    return res;
}
int inv(int x)
{
    return qpow(x,mod-2);
}
int C(int n,int m)
{
    return jie[m]*inv(jie[n])%mod*inv(jie[m-n])%mod;
}
signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin>>n;
    jie[0]=1;
    for(int i=1;i<=n;i++)   jie[i]=jie[i-1]*i%mod;
    int ans=jie[n];
    for(int i=1;i<n;i++)
    {
        ans=(ans+C(i,n)*jie[i]%mod*(jie[n-i]+mod-1)%mod)%mod;
    }
    cout<<ans<<endl;
    return 0;
}

感觉码风还行

总结：这个题顺水推舟就想出来了，但是要注意到 !(n-i) 减一的细节