bzoj 4417 [Shoi2013]超级跳马

3 5

10

题解

#include <cstdio>
#include <cstring>
using namespace std;
int mn;
long long p;
const int mod = 30011;
#define MN 160
struct matrixs {
int m[MN][MN];
void clear() { memset(m, 0, sizeof m); }
matrixs operator * (const matrixs &a) const {
matrixs ans = {};
for (int i = 1; i <= mn; i++)
for (int k = 1; k <= mn; k++)
if (m[i][k])
for (int j = 1; j <= mn; j++)
ans.m[i][j] = (ans.m[i][j] + (long long)m[i][k] * a.m[k][j]) % mod;
return ans;
}
matrixs matrix_pow(long long p) {
matrixs ans,a = (*this);
ans.clear();
for (int i = 1; i <= mn; i++) ans.m[i][i] = 1;
for (; p; a = a * a, p >>= 1)
if (p & 1) ans = ans * a;
return ans;
}
void print() {
for (int i = 1; i <= mn; ++i, puts(""))
for (int j = 1; j <= mn; ++j)
printf("%d ", m[i][j]);
puts("");
}
}a, b, c;
main() {
int n;
scanf("%d %lld", &n, &p);
mn = n * 3;
a.m[1][1] = a.m[1][n * 2 + 1] = 1;
for (int i = 1; i <= n; ++i) {
c.m[n + i][i] = c.m[i][n + i] = c.m[i][i] = 1;
if (i != 1)
c.m[i - 1][i] = c.m[i - 1][n * 2 + i] = 1;
if (i != n)
c.m[i + 1][i] = c.m[i + 1][n * 2 + i] = 1;
c.m[i][n * 2 + i] = 1;
//      c.print();
}
p--;
c = c.matrix_pow(p);
//  c.print();
a = a * c;
//  a.print();
printf("%d\n", a.m[1][n * 3]);
}