Facebook Hacker Cup 2013 Digits War

問題概要

数字iと数字jが戦争状態にある場合、iとjは隣接することはできない。またiとjの間に1つしか別の数字がないという状況も許されない。 このような状況で、桁数がk以下の数字は何通り作ることができるか？

解法

動的計画法＆行列の累乗の計算（繰返二乗法）。初見は簡単と思ったけど、leading zeroの扱いがややこしかった。

ソースコード

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

typedef vector<vector<long long> > matrix;

long long MOD = 1000000007;
int war[10][10];

matrix operator* (const matrix &x, const matrix &y) {
    int n = x.size();
    matrix ret(n, vector<long long>(n, 0));

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int k = 0; k < n; k++) {
                ret[i][j] += x[i][k] * y[k][j] % MOD;
                ret[i][j] %= MOD;
            }

    return ret;
}

vector<long long> operator* (const matrix &x, const vector<long long> &y) {
    int n = y.size();
    vector<long long> ret(n);

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            ret[i] += x[i][j] * y[j] % MOD;
            ret[i] %= MOD;
        }
    return ret;
}

long long solve() {
    long long k;
    cin >> k;

    for (int i = 0; i < 10; i++)
        for (int j = 0; j < 10; j++)
            cin >> war[i][j];

    matrix A(101, vector<long long>(101));
    for (int k = 0; k < 10; k++)
        for (int i = 0; i < 10; i++)
            for (int j = 0; j < 10; j++)
                if (!war[i][k] && !war[k][j] && !war[i][j])
                    A[10*i+k][10*k+j] = 1;

    for (int i = 1; i < 10; i++)
        for (int j = 0; j < 10; j++)
            A[100][10*i+j] = 1;
    A[100][100] = 1;

    vector<long long> x(101);
    x[100] = 9;
    for (int i = 0; i < 10; i++)
        for (int j = 0; j < 10; j++)
            if (!war[i][j])
                x[10*i+j] = 1;

    --k;
    while (k > 0) {
        if (k & 1)
            x = A * x;
        k >>= 1;
        A = A * A;
    }
    
    return x[100];
}

int main() {
    int t;
    scanf("%d", &t);

    for (int i = 0; i < t; i++) {
        printf("Case #%d: ", i+1);
        long long ret = solve();
        cout << ret << endl;
    }

    return 0;
}