hdu 3658(矩陣快速冪)

hdu 3658(矩陣快速冪)

題意：一個長度為m的字符串需要填充，填充字母必須是’A’ ~ ‘Z’，’a’ ~ ‘z’，要求字符串相鄰字符的ascii值的差值≤32，且必須至少存在一個相鄰字符差值等於32。問有多少種填充方式。
題解：直接構造至少存在一個相鄰字符差值等於32的不好做，可以逆著想，先求出差值>=32的所有情況，再求出差值<32的所有情況，兩個結果相減就是解。

#include 
#include 
#include 
using namespace std;
const int MOD = 1000000007;
struct Mat {
    long long g[55][55];
}ori, res, ori2, res2;
long long m;

Mat multiply(Mat x, Mat y) {
    Mat temp;
    for (int i = 0; i < 52; i++)
        for (int j = 0; j < 52; j++) {
            temp.g[i][j] = 0;
            for (int k = 0; k < 52; k++)
                temp.g[i][j] = (temp.g[i][j] + x.g[i][k] * y.g[k][j]) % MOD;
        }
    return temp;
}

void calc1(long long m) {
    while (m) {
        if (m & 1)
            ori2 = multiply(ori2, res2);
        m >>= 1;
        res2 = multiply(res2, res2);
    }
}
void calc2(long long m) {
    while (m) {
        if (m & 1)
            ori = multiply(ori, res);
        m >>= 1;
        res = multiply(res, res);
    }
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%lld", &m);
        memset(res.g, 0, sizeof(res.g));
        memset(ori.g, 0, sizeof(ori.g));
        memset(res2.g, 0, sizeof(res2.g));
        memset(ori2.g, 0, sizeof(ori2.g));
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j <= i + 26; j++)
                res.g[j][i] = res2.g[j][i] = 1;
            res2.g[i + 26][i] = 0;
        }
        for (int i = 26; i < 52; i++) {
            for (int j = 51; j >= i - 26; j--)
                res.g[j][i] = res2.g[j][i] = 1;
            res2.g[i - 26][i] = 0;
        }
        for (int i = 0; i < 52; i++)
            ori.g[0][i] = ori2.g[0][i] = 1;
        calc1(m - 1);
        calc2(m - 1);
        long long ans1 = 0, ans2 = 0;
        for (int i = 0; i < 52; i++) {
            ans1 = (ans1 + ori.g[0][i]) % MOD;
            ans2 = (ans2 + ori2.g[0][i]) % MOD;
        }
        printf("%lld\n", (ans1 + MOD - ans2) % MOD);
    }
    return 0;
}