HDU 5564 - Clarke and digits (dp + 矩阵快速幂 | 被7整除相邻不为k)
## 题意 ##
长度为[l, r]的数，被7整除相邻位不为k的个数。
## 思路 ##
感觉这题很神奇。
dp[i][j][k]表示长度为i余数为j最后一位为k的个数。
那么dp[i+1][j*10%7][x] += dp[i][j][k]
由于数据范围太大，用矩阵快速幂。
这里就有个很神奇的东西了，把（余数，尾数）压缩成一个状态，用mat[state1][state2]表示state1可以向state2转移，正好能利用矩阵乘法。
求和也很神奇。
加一维求和，求和的目标是所有mat[0][k]都加到mat[0][70]上。
总之很神奇，似懂非懂。
## 代码 ##
#include <stack>
#include <cstdio>
#include <list>
#include <cassert>
#include <set>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <functional>
#include <cstring>
#include <algorithm>
#include <cctype>
//#pragma comment(linker, "/STACK:102400000,102400000")
#include <string>
#include <map>
#include <cmath>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define SZ(x) (int)x.size()
#define Lowbit(x) ((x) & (-x))
#define MP(a, b) make_pair(a, b)
#define MS(p, num) memset(p, num, sizeof(p))
#define PB push_back
#define X first
#define Y second
#define ROP freopen("input.txt", "r", stdin);
#define MID(a, b) (a + ((b - a) >> 1))
#define LC rt << 1, l, mid
#define RC rt << 1|1, mid + 1, r
#define LRT rt << 1
#define RRT rt << 1|1
#define FOR(i, a, b) for (int i=(a); (i) < (b); (i)++)
#define FOOR(i, a, b) for (int i = (a); (i)<=(b); (i)++)
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;
const int MAXN = 71;
const int MOD = 1e9 + 7;
const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
const int seed = 131;
int cases = 0;
typedef std::pair<int, int> pii;
struct Matrix
{
int mat[MAXN][MAXN];
Matrix() { MS(mat, 0); }
void init() { for (int i = 0; i < MAXN; i++) mat[i][i] = 1; }
Matrix operator * (const Matrix &rhs)
{
Matrix ret;
FOR(i, 0, MAXN) FOR(j, 0, MAXN) FOR(k, 0, MAXN) ret.mat[i][j] = (ret.mat[i][j] + (LL)mat[i][k]*rhs.mat[k][j]) % MOD;
return ret;
}
Matrix operator ^ (int n) const
{
Matrix ret, a;
ret.init(); memcpy(a.mat, this->mat, sizeof this->mat);
while (n)
{
if (n & 1) ret = ret * a;
a = a * a;
n >>= 1;
}
return ret;
}
};
int main()
{
//ROP;
int T;
scanf("%d", &T);
while (T--)
{
Matrix transfer_matrix;
transfer_matrix.init();
Matrix a;
for (int i = 1; i < 10; i++)
{
int u = i%7*10 + i;
a.mat[0][u] = 1;
}
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
for (int i = 0; i < 7; i++)
for (int j = 0; j < 10; j++)
{
int u = i*10 + j;
for (int ii = 0; ii < 7; ii++)
for (int jj = 0; jj < 10; jj++) if (j + jj != k)
{
int v = ii*10 + jj;
transfer_matrix.mat[u][v] = ((i*10 + jj) % 7 == ii);
}
}
for (int i = 0; i < 10; i++) transfer_matrix.mat[i][70] = 1;
Matrix ans1 = a * (transfer_matrix ^ r);
Matrix ans2 = a * (transfer_matrix ^ (l - 1));
printf("%d\n", (ans1.mat[0][70] - ans2.mat[0][70] + MOD) % MOD);
}
return 0;
}