## 2013年2月25日月曜日

### Facebook Hacker Cup 2013 Digits War

ソースコード
```#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;
}
```