题解：P10376 [GESP202403 六级] 游戏

思路：

先写出暴力的搜索，然后改为记忆化搜索。

暴力的搜索就是暴力向下搜 $n$ 减去 $a$ 和 $n$ 减去 $b$ 的游戏操作序列的总数，暴力搜索代码如下。

long long dfs(long long x){
	if(x<=c)return 1;
	return (dfs(x-a)%mod+dfs(x-b)%mod)%mod;
}

然后改为记忆化搜索，定义一个数组存结果，如果现在搜索的这个数已经被搜索过了就自己访问数组，如果没有就先搜索，搜索完后赋值，这样就可以防止重复地搜索一个数，记忆化搜索代码如下。

long long dfs(long long x){
	if(x<=c)return 1;
	if(an[x]!=0)return an[x];// 如果有值直接返回
	return an[x]=(dfs(x-a)%mod+dfs(x-b)%mod)%mod;// 如果没有进行搜索并赋值
}

完整代码：

#include<bits/stdc++.h>
using namespace std;
long long an[200005]={0};
long long n,c,b,a;
const int mod=1e9+7;// 模 1e9+7
long long dfs(long long x){
	if(x<=c)return 1;
	if(an[x]!=0)return an[x];// 如果有值直接返回
	return an[x]=(dfs(x-a)%mod+dfs(x-b)%mod)%mod;// 如果没有进行搜索并赋值
}
int main(){
	cin>>n>>a>>b>>c;
	cout<<dfs(n);
	return 0;
}