HDU 5564 - Clarke and digits (dp + 矩阵快速幂 | 被7整除相邻不为k)

Nov 22, 2015


## 题意 ##

长度为[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;
}