斗地主 题解

​ 由于这一回合选什么牌对之后回合选牌并没有影响，所以我们可以考虑使用 $\text{dp}\backslash text\{dp\}$来解决问题。

​ 我们设计这么一种状态 $f_{i,j}f\_\{i,j\}$ 表示前 $ii$ 回合，选的牌分值是 $jj$ 的方案数。

​ 那么枚举这一回合的牌，$\text{dp}\backslash text\{dp\}$转移式就是：

​ 关于答案的统计，我们发现 $kk$ 的值域很小，所以暴力统计的复杂度为$O(nmk)O(nmk)$。

#include<bits/stdc++.h>
using namespace std;
#define P 1000000007
#define M 105
int n,m,k,a[M],dp[M][M];
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=m;++i)scanf("%d",&a[i]);
	dp[0][0]=1;
	for(int i=0;i<n;++i){
		for(int j=0;j<k;++j)
			for(int l=1;l<=m;++l){
				dp[i+1][(j+a[l])%k]=(dp[i+1][(j+a[l])%k]+dp[i][j])%P;
			}
	}
	int ans=0;
	for(int i=0;i<k;++i){
		int tp=i,f=0;
		while(tp){
			if(tp%10==9||tp%10==7)f=1;
			tp/=10;
		}
		if(f)ans=(ans+dp[n][i])%P;
	}printf("%d",ans);
}