第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
样例解释
无
首先，根据题意，我们先初始化，后面方便d
1.筛除不含4，7的数
2.去重
3.分类-4类
1) 4开头4结尾
2) 4开头7结尾
3) 7开头4结尾
4) 7开头7结尾
然后就很容易定出dp了
f(i, j): 当前已经构造的长度是i，并且第i个数是第j类
假设
cnt1表示 有多少个第一类
cnt2表示有多少个第二类
cnt3，cnt4以此类推
那么可以推出转移方程
f(L, 1)=( f(L-1, 1)+f(L-1, 3) ) * cnt1
f(L, 2)=( f(L-1, 1)+f(L-1, 3) ) * cnt2
f(L, 3)=( f(L-1, 2)+f(L-1, 4) ) * cnt3
f(L, 4)=( f(L-1, 2)+f(L-1, 4) ) * cnt4
举个例：
f(L, 3)表示长度为L，第L个数是第3类的（7开头，4结尾）
那么 L 肯定由 L-1 转移转移过来的。由于第L个数是7开头的，那么L-1个数肯定是7结尾的，然后我们考虑第L这一位，它可以从7开头7结尾的数中任选一个，也就是要乘上cnt3
剩余的同上。
推完dp后，可以开始矩阵加速了
由于平常的矩阵都是一维的，这里却是二维，不好算
我们考虑降维，我们把第一维拆分成阶段，（矩阵不断递推，不就算作为阶段么）第二维成为矩阵中的内容
[f1, f2, f3, f4]
假设当前已构造的长度是L
f1:长度是L的第1类的方案数
f2:长度是L的第2类的方案数
f3:长度是L的第3类的方案数
f4:长度是L的第4类的方案数
目标矩阵长度就是L+1
[f1', f2', f3', f4']
f1':长度是L+1的第1类的方案数
......
f1' = cnt1*f1+ cnt1*f3
f2' = cnt2*f1+ cnt2*f3
......（跟dp一个样，没啥好补充的了）
[f1, f2, f3, f4] * [B] = [f1', f2', f3', f4']
[B]:（根据上面的式子即可求出）
[cnt1, cnt2, 0, 0 ]
[0, 0, cnt3, cnt4 ]
[cnt1, cnt2, 0, 0]
[0, 0, cnt3, cnt4]
答案：
[f1, f2, f3, f4]*[B]^(L-1)
ans=f1+f2+f3+f4
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=55, Mod=1234567891;
struct mp
{
int n, m;
int a[N][N];
void init(int row, int col, bool isI)
{
n=row, m=col;
memset(a, 0, sizeof a);
if (isI)
for (int i=1; i<=row; i++) a[i][i]=1;
}
}A, B;
mp operator * (const mp A, const mp B)
{
mp C;
C.init(A.n, B.m, 0);
for (int i=1; i<=A.n; i++)
for (int j=1; j<=B.m; j++)
for (int k=1; k<=A.m; k++)
C.a[i][j]=(C.a[i][j]+A.a[i][k]*B.a[k][j])%Mod;
return C;
}
mp qpow_mp(mp A, int k)
{
mp res;
res.init(A.n, A.m, 1);
while (k>0)
{
if (k&1) res=res*A;
A=A*A;
k>>=1;
}
return res;
}
int n, m, L, x, a[N], cnt[N];
signed main()
{
scanf("%lld%lld", &n, &L);
for (int i=1; i<=n; i++)
{
int t=0;
bool ok=1;
scanf("%lld", &x);
t=x;
while (t>0)
{
if (t%10!=4 && t%10!=7)
{
ok=0;
break;
}
t/=10;
}
if (ok) a[++m]=x;
}
// printf("{%d}", m);
sort(a+1, a+1+m);
m=unique(a+1, a+1+m)-a-1;
// printf("{%d}", m);
for (int i=1; i<=m; i++)
{
int t=a[i], fst=0, lst=0;
while (t>0)
{
if (fst==0) fst=t%10;
lst=t%10;
t/=10;
}
if (fst==4 && lst==4) cnt[1]++;
if (fst==4 && lst==7) cnt[2]++;
if (fst==7 && lst==4) cnt[3]++;
if (fst==7 && lst==7) cnt[4]++;
}
A.init(1, 4, 0);
A.a[1][1]=cnt[1], A.a[1][2]=cnt[2], A.a[1][3]=cnt[3], A.a[1][4]=cnt[4];
B.init(4, 4, 0);
B.a[1][1]=cnt[1], B.a[1][2]=cnt[2], B.a[1][3]=0, B.a[1][4]=0;
B.a[2][1]=0, B.a[2][2]=0, B.a[2][3]=cnt[3], B.a[2][4]=cnt[4];
B.a[3][1]=cnt[1], B.a[3][2]=cnt[2], B.a[3][3]=0, B.a[3][4]=0;
B.a[4][1]=0, B.a[4][2]=0, B.a[4][3]=cnt[3], B.a[4][4]=cnt[4];
A=A*qpow_mp(B, L-1);
printf("%lld", (((A.a[1][1]+A.a[1][2])%Mod+A.a[1][3])%Mod+A.a[1][4])%Mod);
return 0;
}
标签：f1,cnt,f3,int,矩阵,f2,长度,幸运,dp From： https://www.cnblogs.com/didiao233/p/18365985