游游的排列统计

游游的排列统计

题目描述

​ 游游想知道，有多少个长度为n的排列满足任意两个相邻元素之和都不是素数。你能帮帮她吗？

​ 我们定义，长度为n的排列值一个长度为n的数组，其中1到n每个元素恰好出现了一次。

输入描述:

1
2
一个正整数n。
2≤n≤10

输出描述:

1
满足条件的排列数量。

示例1

输入

1
5

输出

1
4

说明

1
2
3
4
5
共有以下 4 种合法排列：
[1,3,5,4,2]
[3,1,5,4,2]
[2,4,5,1,3]
[2,4,5,3,1]

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

img 很小，img，计算量最多为 img，况且其中有回溯现象，所以计算量大约不超过 img。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, ans, a[1001], d[1001];
bool check(int x) {//判断素数
    if (x == 1) return true;
    for (int i = 2; i * i <= x; i ++ )
        if (x % i == 0)
            return true;
    return false;
}
void dfs(int x) {
    if (x > n) {//x>n时，表示有一个序列达成要求，ans++
        ans ++ ;
        return;
    }
    for (int i = 1; i <= n; i ++ )
        if (!d[i]) {//判断数字有没有被用，如果被用，进行下一项
            d[i] = 1;//将数字标记为已用
            if (x == 1 || check(i + a[x - 1])) {//判断相邻是不是素数
                a[x] = i;//符合条件的话进行添加
                dfs(x + 1);
            }
            d[i] = 0;
        }
}
signed main() {
    cin >> n;
    dfs(1);
    cout << ans;
}