我心情愉悦地提交了,然后80.不知道咋了。求助
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 205;
const int mod = 1000000007;
struct mat {
unsigned long long number[MAXN][MAXN], n, m;
mat operator * (mat B){
mat answer;
answer.n = n, answer.m = B.m;
for (int i = 1; i <= answer.n; ++i)
for (int j = 1; j <= answer.m; ++j) {
answer.number[i][j] = 0;
for (int k = 1; k <= m; ++k) {
answer.number[i][j] += number[i][k] * B.number[k][j];
answer.number[i][j] %= mod;
}
}
return answer;
}
};
mat fastpow (mat A, long long k) {
return k == 1 ? A : (k % 2 == 0 ? fastpow (A * A, k / 2) : fastpow (A * A, k / 2) * A);
}
int main () {
mat T1, T2;
T1.n = 2; T1.m = 2;
T1.number[1][1]=0;T1.number[1][2]=1;
T1.number[2][1]=1;T1.number[2][2]=1;
T2.n = 2; T2.m = 1;
T2.number[1][1]=1;
T2.number[2][1]=1;
unsigned long long num; cin >> num;
if (num <= 2)
cout << 1 << endl;
else cout << (fastpow (T1, num - 2) * T2).number[2][1] << endl;
return 0;
}
hack掉这个傻逼的数据:
输入:188363182
输出:65748392011234567