P8143 题解

g_p_c_r · 2022-02-12 11:37:09 · 题解

思路

1. 当 n=1 时，答案是 1
2. 当 n=2 时，答案是 1
3. 当 n=3 时，答案是 3
4. 当 n=4 时，答案是 12

不难发现规律：答案是 \frac{n!}{2}

证明：1 ∼ n 中有 n! 种排序，有一半不行，所以是 \frac{n!}{2}

注意：

1. 不要除以 2 取模，同余没有可除性，只要在乘 2 的时候将 2 跳过即可。
2. 10年oi一场空，不开longlong见祖宗

Code

#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
long long ans=1;
int main(){
    int n;
    cin>>n;
    for(int i=1; i<=n; i++){
        if(i==2)continue;
        ans*=i;ans%=mod;
    }
    cout<<ans;
}