牛客练习赛B题 筱玛的排列（找递推规律）

链接：https://ac.nowcoder.com/acm/contest/342/B
来源：牛客网

筱玛的排列

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

筱玛是一个快乐的男孩子。

筱玛在一次数学考试中看到了这样一道题：

聪明的筱玛当然一眼就秒掉了这道题，现在他想来考考你。

输入描述:

一行一个整数 n。

输出描述:

一行一个整数，表示模 998244353 意义下的答案。

示例1

输入

4

输出

2

说明

3 1 4 2
2 4 1 3

只有以上这两个合法的排列 A。

备注:

1 ≤ n ≤ 10

 

多手写（或者代码敲）几组样例，

我罗列出前8组数据

n  1　　2　　3　　4　　5　　6　　7　　8　　

a  1　　0　　0　　2　　3　　0　　0　　12

 

可以寻找出 a[i]=a[i-4]*(i-2)的规律

其a[0]=a[1]= 1

然后可以预处理一下，直接输出答案了。

 

我的AC代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <vector>

#define sz(a) int(a.size())

#define all(a) a.begin(), a.end()

#define rep(i,x,n) for(int i=x;i<n;i++)

#define repd(i,x,n) for(int i=x;i<=n;i++)

#define pii pair<int,int>

#define pll pair<long long ,long long>

#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

#define MS0(X) memset((X), 0, sizeof((X)))

#define MSC0(X) memset((X), '\0', sizeof((X)))

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define gg(x) getInt(&x)

using namespace std;

typedef long long ll;

inline void getInt(int* p);

const int maxn=;

const int inf=0x3f3f3f3f;

/*** TEMPLATE CODE * * STARTS HERE ***/

ll dp[maxn];

const ll mod=998244353ll;

ll n;

int main()

{

    dp[]=dp[]=1ll;

    repd(i,,1e6)

    {

        dp[i]=dp[i-]*(i-);

        dp[i]=(dp[i]+mod)%mod;

    }

    while(~scanf("%lld",&n))

    {

        printf("%lld\n",dp[n] );

    }

    return ;

}

inline void getInt(int* p) {

    char ch;

    do {

        ch = getchar();

    } while (ch == ' ' || ch == '\n');

    if (ch == '-') {

        *p = -(getchar() - '');

        while ((ch = getchar()) >= '' && ch <= '') {

            *p = *p *  - ch + '';

        }

    }

    else {

        *p = ch - '';

        while ((ch = getchar()) >= '' && ch <= '') {

            *p = *p *  + ch - '';

        }

    }

}