[题目传送门](https://www.luogu.com.cn/problem/P10099)
## ##
本题解有借鉴其他题解的思路。

考虑已经填完了后 $ i - 1 $ 位，要填倒数第 $ i $ 位。

对于每个 $ x \in A $，
如果 $ x $ 上一次出现的位置与 $ i $ 的距离 $ \ge x $，
第 $ i $ 位就可以填 $ x $。

看看数据范围，肯定要状压 dp。

但是压缩状态函数太难写，再看数据范围：$ m \le 8 $，$ n \le 100 $。


$ \begin{aligned}
  100 \times 8! &= 100 \times 40320 \\
                &= 4032000 \\
                &< 5000000 B\\
                &<50 MB \\
                &<512 MB
\end{aligned} $


开的下这么大的空间，所以开一个这样的dp数组。
```cpp
dp[105][1][2][3][4][5][6][7][8];

其中第一维表示已经填到第几位，其余第 $ i $ 维表示数字 $ i-1 $ 上一次出现的位置与现在所填的位置的距离。
若该数字上一次出现的距离离 $ \ge i-1 $ 则视为 $ i-1 $。

因为正着写太肝了，所以采用记忆化搜索。如果可以填 $ x $ 那就假设填 $ x $ 往下搜索。

### AC代码 
```cpp
#include<bits/stdc++.h>
using namespace std;
#define p 1000000007l
#define ll long long
int n,m;
ll dp[105][1][2][3][4][5][6][7][8];
bool has[10];//有没有这个数
ll dfs(int dep,int a,int b,int c,int d,int e,int f,int g,int h){//记忆化搜索
	if(~dp[dep][a][b][c][d][e][f][g][h]) return dp[dep][a][b][c][d][e][f][g][h];
	if(dep>n) return 1l;
	int dth[]={0,a+1,b+1,c+1,d+1,e+1,f+1,g+1,h+1};
	ll ret=0;
	//cout<<endl;
	for(int i=1;i<=8;i++)
		if(has[i]&&dth[i]==i){
			dth[i]=0;
			ret=(ret+dfs(dep+1,0,min(dth[2],1),min(dth[3],2),min(dth[4],3),min(dth[5],4),min(dth[6],5),min(dth[7],6),min(dth[8],7)))%p;//min防止溢出
			dth[i]=i;//记得复原
		}
	dp[dep][a][b][c][d][e][f][g][h]=ret;
	//cout<<ret<<endl;
	return ret;
}
int main(){
	cin>>n>>m;
	memset(dp,0xff,sizeof(dp));
	for(int i=1,sum;i<=m;i++){cin>>sum;has[sum]=1;}
	cout<<dfs(1,0,1,2,3,4,5,6,7)<<endl;
	return 0;
}

__不防溢出会 RE！！！__
### 如果只用一个空间会WA

```cpp
#include<bits/stdc++.h>
using namespace std;
#define p 1000000007l
#define ll long long
short n,m;
ll dp[105][1][2][3][4][5][6][7][8];
bool has[10];//有没有这个数
short a[10]={0,0,1,2,3,4,5,6,7};
ll dfs(short dep){//记忆化搜索
	if(~dp[dep][a[1]][a[2]][a[3]][a[4]][a[5]][a[6]][a[7]][a[8]])
		return dp[dep][a[1]][a[2]][a[3]][a[4]][a[5]][a[6]][a[7]][a[8]];
	if(dep>n) return 1l;
	for(int i=1;i<=8;i++) a[i]=(a[i]==i-1?0:a[i]+1);
	ll ret=0;
	for(short i=1;i<=8;i++)
		if(has[i]&&a[i]==0) ret=(ret+dfs(dep+1))%p;
	for(int i=1;i<=8;i++) a[i]=(a[i]==0?i-1:a[i]-1);
	dp[dep][a[1]][a[2]][a[3]][a[4]][a[5]][a[6]][a[7]][a[8]]=ret;
	cout<<ret<<endl;
	return ret;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	memset(dp,0xff,sizeof(dp));
	for(short i=1,sum;i<=m;i++){cin>>sum;has[sum]=1;}
	cout<<dfs(1)<<endl;
	return 0;
}

### 附上我在考场上写的数学算法代码 
对前四个子任务打表分析可得 $ 50 $ 分。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define p 1000000007l
int n,m;
long long a[10],dp[105];
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++) cin>>a[i];
	sort(a+1,a+m+1,less<int>());
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) dp[i]=(dp[i]+(i>a[j]?dp[i-a[j]]:1))%p;
	cout<<dp[n]<<endl;
	return 0;
}