第1题 幸运数 查看测评数据信息

小明认为只有数字4和7是幸运数字，其他数字都不是。

如果一个整数的每个数字都是幸运数字，那么该整数就是幸运整数。

给出一个数组numbers[1...n]。

一个长度为L的幸运数列A[0],A[1],A[2],...A[L-1]必须同时满足：

1、对于0<=i<L, A[i]必须是幸运整数。

2、对于0<=i<L-1，A[i]的最后一个数字必须等于A[i+1]的第一个数字。

3、 对于0<=i<L, 至少存在一个下标j满足A[i] = numbers[j]。

输出有多少个不同的长度为L的幸运序列，答案模1234567891。

提示：对于两个长度都是L的幸运序列A[0], A[1], ..., A[L- 1] 和 B[0], B[1], ..., B[L - 1]，他们被认为是不同序列的条件是：存在一个下标i, 使得A[i] != B[i]

输入格式

第一行，两个整数，n和L。 1<=n<=50, 1<=L<=1e9。

第二行，n个整数，第i个整数是numbers[i], 1<=numbers[i]<=1e9。

输出格式

一个整数

输入/输出例子1 输入：

3 3

47 74 47

输出：

2

输入/输出例子2 输入：

5 47

100 4774 200 747 300

输出：

2

样例解释 无

#include<bits/stdc++.h>
using namespace std;
const long long maxN=10;
long long n,l,a[55],s4e7,s7e4,s4e4,s7e7;
const long long mod=1234567891;
struct matrix{
	int h,l;
	long long jz[maxN][maxN];
	matrix(int r,int c,bool isI){
		h=r,l=c;
		memset(jz,0,sizeof(jz));
		if(isI){
			for(int i=0;i<h;i++){
				jz[i][i]=1;
			}
		}
	}
};
matrix operator * (const matrix &a,const matrix &b){
	matrix c(a.h,b.l,0);
	
	for(int i=0;i<a.h;i++){
		for(int j=0;j<b.l;j++){
			for(int k=0;k<a.l;k++)
			c.jz[i][j]=(c.jz[i][j]+a.jz[i][k]*b.jz[k][j]%mod)%mod;
		}
	}
	return c;
}
matrix powjz(matrix a,long long k){
	matrix ans(a.h,a.l,1);
	for(;k;k>>=1){
		if(k&1){
			ans=ans*a;
		}
		a=a*a;
	}
	return ans;
}
bool pd(long long sb){
	while(sb){
		
		if(sb%10!=7&&sb%10!=4){
			return 1;
		}
		sb/=10;
	}
	return 0;
}
int main(){
	cin>>n>>l;
	int js=0;
	for(int i=0;i<n;i++){
		cin>>a[i];
		if(pd(a[i])){
			a[i]=2000000000;
			js++;
		}
	}
	sort(a,a+n);
	n-=js;
	js=0;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(a[i]==a[j]){
				a[j]=2000000000;
				js++;
			}
		}
	}
	sort(a,a+n);
	n-=js;
	js=0;
	for(int i=0;i<n;i++){
		int en=0,st=0;
		en=a[i]%10;
		long long dt=a[i];
		while(dt/10!=0){
			dt/=10;
		}
		st=dt;
		if(st==4){
			if(en==7){
				s4e7++;
			}else{
				s4e4++;
			} 
		}else{
			if(en==7){
				s7e7++;
			}else{
				s7e4++;
			}
			
		}
	}
	matrix ans(1,2,0);
	ans.jz[0][0]=s4e4+s7e4;
	ans.jz[0][1]=s4e7+s7e7;
	matrix base(2,2,0);
	base.jz[0][0]=s4e4;
	base.jz[0][1]=s4e7;
	base.jz[1][0]=s7e4;
	base.jz[1][1]=s7e7;
	base=powjz(base,l-1);
	ans=ans*base;
	cout<<(ans.jz[0][0]+ans.jz[0][1])%mod;
    return 0;
}