Lang:G++
Edit12345678910111213141516171819202122232425262728293031#include <iostream>#include <bits/stdc++.h>#include <sstream>#include <vector>using namespace std;typedef long long int LL;typedef vector<long long int> vec;typedef vector<vec> mat;const int maxn=1000000+10;const int MOD=1000000007;mat mul(mat A, mat B){mat C(A.size(), vec(B[0].size()));for (unsigned i = 0; i < A.size(); i++)for (unsigned j = 0; j < B[0].size(); j++)for (unsigned k = 0; k < B.size(); k++)C[i][j] = ((C[i][j] + A[i][k] * B[k][j]%MOD) + MOD) % MOD; // 中间会出现负数,所以要先+MOD。return C;}mat pow(mat A, LL n){mat B(A.size(), vec(A.size()));for (unsigned i = 0; i < A.size(); i++)B[i][i] = 1;while (n > 0){if (n & 1) B = mul(B, A);A = mul(A, A);n >>= 1;}