摆书【错排公式】

B.摆书

Description

Quasrain 和 FZ 是好朋友。某天老师交给他们两组相同的书，每组书都是 n 本且不重复。他们需要把这两组书排列到一行 n 个书架上，每个书架上放两本书，且同一个人不能在同一个书架上放两本书。现在他们想知道，每个书架上的两本书都不一样的方案数。这n个书架互相等价，不区分顺序

Input

多组数据，读入到文件结尾。
对于每一组数据，包含一个数 n，意义如题面所示

Output

对于每组数据，输出方案数，对 998244353 取模后的值

Sample Input

    2
    3
    4

Sample Output

    1
    2
    9

Hint

2<=N<=10^5

输入数据不超过 100 行

对于第二组样例：摆放方式有

甲取{1,2,3}，乙取{2,3,1}

甲取{1,2,3}，乙取{3,1,2}

甲取{1,2,3}，乙取{2,3,1}的方案与甲取{2,1,3}，乙取{3,2,1}的方案等价

思路：

上午比赛做这个题耗了好长时间最后还是没做出来确实是没思路漫无目的的找规律

看了题解确实直接推不好推看了几个博客下面这个讲解的还很好：

https://blog.csdn.net/bengshakalakaka/article/details/83420150

现在想想这个题确实是很形象的在描述错排：相同课本不可以放在一起

1 2 9 44 265 ……

AC代码：

#include<stdio.h>
typedef long long LL;
const int MAX=1e5;
const int mod=998244353;
int main()
{
    LL a[MAX+5],n;
    a[2]=1,a[3]=2;
    for(LL i=4;i<=MAX;i++){
        a[i]=(((i-1)%mod)*((a[i-1]+a[i-2])%mod))%mod;
    }
    while(scanf("%lld",&n)){
        printf("%lld
",a[n]%mod);
    }
    return 0;
}