hdu 1757マトリクス高速べき乗
7330 ワード
この問題は悪くなくて、問題を見始めて、道の水の問題だと思って、数分かけて暴捜をして、断固としてruntime error、スタックがあふれています.そこですぐに法則を探して、行列乗算と高速べき乗に変換して解決できることを発見しましたが、審査問題がはっきりしないので、a 0を間違えました...a 9の順番、長い間調整してやっと発見...
/*
* hdu1757/win.cpp
* Created on: 2012-7-9
* Author : ben
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
const int MAX_ORDER = 11;
int MOD;
typedef int typec;
typedef struct MyMatrix {
int order;
typec num[MAX_ORDER][MAX_ORDER];
MyMatrix(int ord) {
order = ord;
}
void init() {
for (int i = 0; i < order; i++) {
for (int j = 0; j < order; j++) {
num[i][j] = 0;
}
}
}
}MyMatrix;
MyMatrix operator*(MyMatrix ma, MyMatrix mb) {
int ord = ma.order;
MyMatrix numc(ord);
numc.init();
int i, j, k;
for (i = 0; i < ord; i++) {
for (j = 0; j < ord; j++) {
for (k = 0; k < ord; k++) {
numc.num[i][j] += ma.num[i][k] * mb.num[k][j];
numc.num[i][j] %= MOD;
}
} }
return numc;
}
MyMatrix mpow(MyMatrix ma, int x) {
int ord = ma.order;
MyMatrix numc(ord);
numc.init();
for (int i = 0; i < ord; i++) {
numc.num[i][i] = 1;
}
for (; x; x >>= 1) {
if (x & 1) {
numc = numc * ma;
}
ma = ma * ma;
}
return numc;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif
int k;
MyMatrix matrix(10);
matrix.init();
for(int i = 0; i < 9; i++) {
matrix.num[i + 1][i] = 1;
}
while(scanf("%d%d", &k, &MOD) == 2) {
for(int i = 9; i >= 0; i--) {
scanf("%d", &matrix.num[i][9]);
}
MyMatrix ret = mpow(matrix, k - 9);
int ans = 0;
for(int i = 1; i < 10; i++) {
ans += (i * ret.num[i][9]) % MOD;
ans %= MOD;
}
printf("%d
", ans);
}
return 0;
}