C 解法, 执行用时: 3ms, 内存消耗: 324K, 提交时间: 2021-12-18 15:29:19

#include<stdio.h>
#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);
}

pypy3 解法, 执行用时: 124ms, 内存消耗: 25884K, 提交时间: 2021-12-10 19:59:45

n, m, k = map(int, input().split())
dp = [0] * k
a = list(map(int, input().split()))
for i in a:
    dp[i] += 1
for i in range(n - 1):
    f = [0] * k
    for j in range(k):
        for _ in a:
            f[(j + _) % k] += dp[j]
    for j in range(k):
        f[j] %= int(1e9 + 7)
    dp = f
ans = 0
for i in range(k):
    if '7' in str(i) or '9' in str(i):
        ans += dp[i]
print(ans % int(1e9 + 7))

C++ 解法, 执行用时: 4ms, 内存消耗: 464K, 提交时间: 2021-12-10 19:06:01

#include<bits/stdc++.h>
using namespace std;
#define N 110
#define MOD 1000000007
int n,m,K,f[N][N],a[N],ans;
int main()
{
	f[0][0]=1;
	cin>>n>>m>>K;
	for(int i=1;i<=m;i++)cin>>a[i];
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)for(int k=0;k<K;k++)f[i][k]=(f[i][k]+f[i-1][(k-a[j]+K)%K])%MOD;
	for(int i=0;i<K;i++)if(i%10==7 || i%10==9)ans=(ans+f[n][i])%MOD;
	cout<<ans<<endl;
}