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

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

筱玛的排列

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

题目描述

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

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

求有多少个长度为 n 的不同的排列 A，满足对于任意的 i 均有 A[A[i]] + i = n + 1。

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

输入描述:

一行一个整数 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), '', 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=1000010;
const int inf=0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
ll dp[maxn];
const ll mod=998244353ll;
ll n;

int main()
{
    dp[0]=dp[1]=1ll;
    repd(i,4,1e6)
    {
        dp[i]=dp[i-4]*(i-2);
        dp[i]=(dp[i]+mod)%mod;
    }    
    while(~scanf("%lld",&n))
    {
        printf("%lld
",dp[n] );
    }
    return 0;
}

inline void getInt(int* p) {
    char ch;
    do {
        ch = getchar();
    } while (ch == ' ' || ch == '
');
    if (ch == '-') {
        *p = -(getchar() - '0');
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 - ch + '0';
        }
    }
    else {
        *p = ch - '0';
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 + ch - '0';
        }
    }
}