题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5564
题意：
求长度在[L,R]范围，并且能整除7的整数的总数。
题解：
考虑最原始的想法：
dp[i][j][k]表示长度为i，并且对7取模得到j的以k结尾的数。
则有状态转移方程dp[i+1][(h*10)+l)%7][k]+=dp[i][h][k'](k+k'!=K).
但是i范围是1~10^9,需要矩阵加速。
这里对dp[i][j][k]的[j][k]两个状态进行压缩，得到转移矩阵mat[70][70],其中mat[s1][s2]表示由状态s2变到状态s1的可行性。
并且由于dp[i][j][k]记录的是长度为i的情况，而我们要求的是所有长度小于等于i的前缀和，所以，我们还要加一行一列来计算所有模7等于零的数的个数。
代码：
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std; const int maxn = ;
const int mod = 1e9 + ;
typedef long long LL; struct Matrix {
LL mat[maxn][maxn];
Matrix() { memset(mat, , sizeof(mat)); }
friend Matrix operator *(const Matrix& A, const Matrix& B);
friend Matrix operator ^(Matrix A, int n);
}; Matrix operator *(const Matrix& A, const Matrix& B) {
Matrix ret;
for (int i = ; i < maxn; i++) {
for (int j = ; j < maxn; j++) {
for (int k = ; k < maxn; k++) {
ret.mat[i][j] += A.mat[i][k] * B.mat[k][j] % mod;
ret.mat[i][j] %= mod;
}
}
}
return ret;
} Matrix operator ^(Matrix A, int n) {
Matrix ret;
for (int i = ; i < maxn; i++) ret.mat[i][i] = ;
while (n) {
if (n & ) ret = ret*A;
A = A*A;
n /= ;
}
return ret;
} int L, R, K; int main() {
int tc;
scanf("%d", &tc);
while (tc--) {
scanf("%d%d%d", &L, &R, &K); L--;
Matrix A, B;
//转移矩阵
for (int i = ; i < ; i++) {
for (int j = ; j < ; j++) {
int x1 = i / , y1 = i % ;
int x2 = j / , y2 = j % ;
if (y1 + y2 == K) continue;
if ((x2* + y1) % == x1) A.mat[i][j] = ;
}
}
//计算前缀和
for (int i = ; i < ; i++) A.mat[][i] = ;
A.mat[][] = ; //初始向量
for (int i = ; i < ; i++) B.mat[(i%)*+i][]++; Matrix AR = A^R, AL = A^L;
Matrix BR = AR*B, BL = AL*B;
LL ans = BR.mat[][] - BL.mat[][];
printf("%lld\n", (ans%mod+mod)%mod);
}
return ;
}