求问深搜

题目：

Alien 的思想真的很诡异。 对于一个 1..N 的排列，Alien 们会把它们全部+1，变成 2..N+1 的 Alien 排列，然后考虑这个排列的优美程度。我们称 Alien 排列的第 i 个数为 Ai，一个排列的是优美的当且仅当对于 i=1..N，i 可以整除 Ai。

现在 Alien 给出一个 N，请你求一下 N 长度的优美排列个数。

Input

一行一个数 N，表示长度为 N。

Output

一行一个数 Ret，表示优美排列个数。

Samples

输入数据

5

输出数据

3

数据范围：

对于 30%数据 N≤10

对于 100%数据 N≤3000

两份代码：

#include <bits/stdc++.h>
using namespace std;
int n,daan;
bool p[3001];

void dfs(int dep)
{
    if(dep>n)
    {
        daan++; 
        return ;
    }
    for(int i=max(dep,2);i<=n+1;i+=dep)
    {
        if(!p[i])
        {
            p[i]=1;
            dfs(dep+1);
            p[i]=0;
        }
    }
}
int main()
{
    cin>>n;
    dfs(1);
    cout<<daan;
    return 0;
}
//从小到大搜索TLE了

#include <bits/stdc++.h>
using namespace std;
int n,daan;
bool p[3001];

void dfs(int dep)
{
    if(dep==0)
    {
        daan++; 
        return ;
    }
    for(int i=max(2,dep);i<=n+1;i+=dep)
    {
        if(!p[i])
        {
            p[i]=1;
            dfs(dep-1);
            p[i]=0;
        }
    }
}
int main()
{
    cin>>n;
    dfs(n);
    cout<<daan;
    return 0;
}
//从大到小搜索为什么就能过？？

没有用 latex,见谅