1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <queue> 7 #include <vector> 8 #include <stack> 9 #include <map> 10 #include <set> 11 #include <cmath> 12 #include <cctype> 13 #include <ctime> 14 15 using namespace std; 16 17 #define REP(i, n) for (int i = 0; i < (n); ++i) 18 #define eps 1e-9 19 #define SZ(x) ((int)x.size()) 20 #define PI acos(-1.0) 21 22 typedef long long ll; 23 typedef unsigned long long ull; 24 typedef pair<int, int> pii; 25 int k, b, n, mod; 26 struct Matrix { ll det[4][4]; }; 27 Matrix ans, ans_t, mat_t; 28 29 Matrix mul(Matrix x, Matrix y) { 30 Matrix ret; memset(ret.det, 0, sizeof(ret.det)); 31 for (int i = 0; i < 4; ++i) { 32 for (int k = 0; k < 4; ++k) { 33 if (x.det[i][k] == 0) { continue; } 34 for (int j = 0; j < 4; ++j) { 35 ret.det[i][j] = (ret.det[i][j] + x.det[i][k] * y.det[k][j]) % mod; 36 } 37 } 38 } 39 return ret; 40 } 41 void solve(ll x) { 42 while (x) { 43 if (x & 1) { ans_t = mul(mat_t, ans_t); } 44 mat_t = mul(mat_t, mat_t); x >>= 1; 45 } 46 } 47 48 int main() { 49 #ifdef __AiR_H 50 freopen("in.txt", "r", stdin); 51 // freopen("out.txt", "w", stdout); 52 #endif // __AiR_H 53 while (scanf("%d %d %d %d", &k, &b, &n, &mod) != EOF) { 54 memset(mat_t.det, 0, sizeof(mat_t.det)); 55 mat_t.det[0][1] = mat_t.det[1][0] = mat_t.det[1][1] = 1; 56 memset(ans_t.det, 0, sizeof(ans_t.det)); 57 ans_t.det[0][0] = ans_t.det[1][1] = 1; 58 if (k) { solve(k); } memset(mat_t.det, 0, sizeof(mat_t.det)); 59 for (int i = 0; i < 2; ++i) { 60 for (int j = 0; j < 2; ++j) { 61 mat_t.det[i][j] = ans_t.det[i][j]; 62 } 63 mat_t.det[i][i + 2] = mat_t.det[i + 2][i + 2] = 1; 64 } 65 memset(ans_t.det, 0, sizeof(ans_t.det)); 66 for (int i = 0; i < 4; ++i) { ans_t.det[i][i] = 1; } 67 if (n) { solve(n); } ans = ans_t; 68 memset(mat_t.det, 0, sizeof(mat_t.det)); 69 mat_t.det[0][1] = mat_t.det[1][0] = mat_t.det[1][1] = 1; 70 memset(ans_t.det, 0, sizeof(ans_t.det)); 71 ans_t.det[0][0] = ans_t.det[1][1] = 1; 72 if (b) { solve(b); } 73 for (int i = 0; i < 2; ++i) { 74 for (int j = 0; j < 2; ++j) { 75 ans.det[i][j] = ans.det[i][j + 2]; 76 ans.det[i][j + 2] = ans.det[i + 2][j] = 0; 77 ans.det[i + 2][j + 2] = 0; 78 } 79 } 80 ans = mul(ans, ans_t); 81 printf("%lld ", ans.det[0][1]); 82 } 83 return 0; 84 }
3 HDU 1757 A Simple Math Problem
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <queue> 7 #include <vector> 8 #include <stack> 9 #include <map> 10 #include <set> 11 #include <cmath> 12 #include <cctype> 13 #include <ctime> 14 #include <bitset> 15 16 using namespace std; 17 18 #define REP(i, n) for (int i = 0; i < (n); ++i) 19 #define eps 1e-9 20 21 typedef long long ll; 22 typedef pair<int, int> pii; 23 24 const int INF = 0x7fffffff; 25 struct Matrix { ll det[20][20]; }; 26 const int mod = 1000; 27 Matrix mat_t, mat, ans; 28 int n, m, q, a, b, k; 29 30 Matrix mul(Matrix x, Matrix y) { 31 Matrix ret; memset(ret.det, 0, sizeof(ret.det)); 32 for (int i = 0; i < n; ++i) { 33 for (int k = 0; k < n; ++k) { 34 if (x.det[i][k] == 0) { continue; } 35 for (int j = 0; j < n; ++j) { 36 ret.det[i][j] = (ret.det[i][j] + x.det[i][k] * y.det[k][j]) % mod; 37 } 38 } 39 } 40 return ret; 41 } 42 void solve(ll x) { 43 mat = ans = mat_t; 44 while (x) { 45 if (x & 1) { ans = mul(mat, ans); } 46 mat = mul(mat, mat); x >>= 1; 47 } 48 } 49 50 int main() { 51 #ifdef __AiR_H 52 freopen("in.txt", "r", stdin); 53 // freopen("out.txt", "w", stdout); 54 #endif // __AiR_H 55 while (scanf("%d %d", &n, &m) != EOF) { 56 if (!n && !m) { break; } memset(mat_t.det, 0, sizeof(mat_t.det)); 57 for (int i = 0; i < m; ++i) { 58 scanf("%d %d", &a, &b); mat_t.det[a][b] = 1; 59 } 60 scanf("%d", &q); 61 while (q--) { 62 scanf("%d %d %d", &a, &b, &k); 63 if (k == 0 && a != b) { printf("0 "); continue; } 64 if (k == 0) { printf("1 "); continue; } 65 solve(k - 1); printf("%d ", ans.det[a][b]); 66 } 67 } 68 return 0; 69 }
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <queue> 7 #include <vector> 8 #include <stack> 9 #include <map> 10 #include <set> 11 #include <cmath> 12 #include <cctype> 13 #include <ctime> 14 15 using namespace std; 16 17 #define REP(i, n) for (int i = 0; i < (n); ++i) 18 #define eps 1e-9 19 #define SZ(x) ((int)x.size()) 20 #define PI acos(-1.0) 21 22 typedef long long ll; 23 typedef unsigned long long ull; 24 typedef pair<int, int> pii; 25 const int maxn = 1e4; 26 const int mod = 2008; 27 struct Matrix { int det[30][30]; }; 28 Matrix mat_t; 29 Matrix mat[maxn]; 30 vector<ll> v; 31 ll p1[maxn], p2[maxn]; 32 int n, q, t1, t2, id1, id2, ans; 33 ll v1, v2; 34 35 Matrix mul(Matrix x, Matrix y) { 36 Matrix ret; memset(ret.det, 0, sizeof(ret.det)); 37 for (int i = 0; i < 30; ++i) { 38 for (int k = 0; k < 30; ++k) { 39 if (x.det[i][k] == 0) { continue; } 40 for (int j = 0; j < 30; ++j) { 41 ret.det[i][j] = (ret.det[i][j] + x.det[i][k] * y.det[k][j]) % mod; 42 } 43 } 44 } 45 return ret; 46 } 47 int get_id(ll x) { 48 int ret = lower_bound(v.begin(), v.end(), x) - v.begin(); 49 if (ret == (int)v.size() || v[ret] != x) { return -1; } return ret; 50 } 51 52 int main() { 53 #ifdef __AiR_H 54 freopen("in.txt", "r", stdin); 55 // freopen("out.txt", "w", stdout); 56 #endif // __AiR_H 57 while (scanf("%d", &n) != EOF) { 58 v.clear(); 59 for (int i = 0; i < n; ++i) { 60 scanf("%lld %lld", &p1[i], &p2[i]); 61 v.push_back(p1[i]); v.push_back(p2[i]); 62 } 63 sort(v.begin(), v.end()); 64 v.erase(unique(v.begin(), v.end()), v.end()); 65 memset(mat_t.det, 0, sizeof(mat_t.det)); 66 for (int i = 0; i < n; ++i) { 67 id1 = get_id(p1[i]); id2 = get_id(p2[i]); 68 ++mat_t.det[id1][id2]; 69 } 70 mat[1] = mat_t; 71 for (int i = 2; i < maxn; ++i) { mat[i] = mul(mat[i - 1], mat_t); } 72 scanf("%d", &q); 73 while (q--) { 74 scanf("%lld %lld %d %d", &v1, &v2, &t1, &t2); 75 id1 = get_id(v1); id2 = get_id(v2); 76 if (id1 == -1 || id2 == -1) { printf("0 "); continue; } 77 ans = 0; 78 for (int i = t1; i <= t2; ++i) { 79 if (i == 0) { continue; } 80 ans += mat[i].det[id1][id2]; ans %= mod; 81 } 82 printf("%d ", ans); 83 } 84 } 85 return 0; 86 }
6 HDU 2256 Problem of Precision
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <queue> 7 #include <vector> 8 #include <stack> 9 #include <map> 10 #include <set> 11 #include <cmath> 12 #include <cctype> 13 #include <ctime> 14 #include <ext/rope> 15 16 using namespace std; 17 using namespace __gnu_cxx; 18 19 #define REP(i, n) for (int i = 0; i < (n); ++i) 20 #define eps 1e-9 21 #define SZ(x) ((int)x.size()) 22 #define PI acos(-1.0) 23 24 typedef long long ll; 25 typedef pair<int, int> pii; 26 const ll mod = 1024; 27 28 struct Matrix { ll det[2][2]; }; 29 Matrix ans, mat; 30 int T, n; 31 32 Matrix mul(Matrix x, Matrix y) { 33 Matrix ret; memset(ret.det, 0, sizeof(ret.det)); 34 for (int i = 0; i < 2; ++i) { 35 for (int k = 0; k < 2; ++k) { 36 if (x.det[i][k] == 0) { continue; } 37 for (int j = 0; j < 2; ++j) { 38 ret.det[i][j] = (ret.det[i][j] + x.det[i][k] * y.det[k][j]) % mod; 39 } 40 } 41 } 42 return ret; 43 } 44 void solve(ll x) { 45 while (x) { 46 if (x & 1) { ans = mul(mat, ans); } 47 mat = mul(mat, mat); x >>= 1; 48 } 49 } 50 51 int main() { 52 #ifdef __AiR_H 53 freopen("in.txt", "r", stdin); 54 // freopen("out.txt", "w", stdout); 55 #endif // __AiR_H 56 scanf("%d", &T); 57 while (T--) { 58 scanf("%d", &n); 59 if (n == 1) { printf("9 "); continue; } 60 ans.det[0][0] = 5; ans.det[1][0] = 2; 61 mat.det[0][0] = 5; mat.det[0][1] = 12; 62 mat.det[1][0] = 2; mat.det[1][1] = 5; 63 solve(n - 1); ans.det[0][0] *= 2; --ans.det[0][0]; 64 ans.det[0][0] %= mod; 65 if (ans.det[0][0] < 0) { ans.det[0][0] += mod; } 66 printf("%d ", ans.det[0][0]); 67 } 68 return 0; 69 }
7 HDU 2276 Kiki & Little Kiki 2
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <queue> 7 #include <vector> 8 #include <stack> 9 #include <map> 10 #include <set> 11 #include <cmath> 12 #include <cctype> 13 #include <ctime> 14 15 using namespace std; 16 17 #define REP(i, n) for (int i = 0; i < (n); ++i) 18 #define eps 1e-9 19 #define SZ(x) ((int)x.size()) 20 #define PI acos(-1.0) 21 22 typedef long long ll; 23 typedef unsigned long long ull; 24 typedef pair<int, int> pii; 25 const int maxn = 110; 26 const int mod = 2; 27 struct Matrix { int det[100][100]; }; 28 Matrix ans, mat; 29 int n, m; 30 char s[maxn]; 31 32 Matrix mul(Matrix x, Matrix y) { 33 Matrix ret; memset(ret.det, 0, sizeof(ret.det)); 34 for (int i = 0; i < n; ++i) { 35 for (int k = 0; k < n; ++k) { 36 if (x.det[i][k] == 0) { continue; } 37 for (int j = 0; j < n; ++j) { 38 ret.det[i][j] = (ret.det[i][j] + x.det[i][k] * y.det[k][j]) % mod; 39 } 40 } 41 } 42 return ret; 43 } 44 void solve(ll x) { 45 while (x) { 46 if (x & 1) { ans = mul(mat, ans); } 47 mat = mul(mat, mat); x >>= 1; 48 } 49 } 50 51 int main() { 52 #ifdef __AiR_H 53 freopen("in.txt", "r", stdin); 54 // freopen("out.txt", "w", stdout); 55 #endif // __AiR_H 56 while (scanf("%d %s", &m, s) != EOF) { 57 n = strlen(s); memset(ans.det, 0, sizeof(ans.det)); 58 for (int i = 0; i < n; ++i) { 59 if (s[i] == '1') { ans.det[i][0] = 1; } 60 } 61 memset(mat.det, 0, sizeof(mat.det)); 62 mat.det[0][0] = mat.det[0][n - 1] = 1; 63 for (int i = 1; i < n; ++i) { 64 mat.det[i][i] = mat.det[i][i - 1] = 1; 65 } 66 solve(m); 67 for (int i = 0; i < n; ++i) { 68 printf(i == n - 1 ? "%d " : "%d", ans.det[i][0]); 69 } 70 } 71 return 0; 72 }
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <queue> 7 #include <vector> 8 #include <stack> 9 #include <map> 10 #include <set> 11 #include <cmath> 12 #include <cctype> 13 #include <ctime> 14 15 using namespace std; 16 17 #define REP(i, n) for (int i = 0; i < (n); ++i) 18 #define eps 1e-9 19 #define SZ(x) ((int)x.size()) 20 #define PI acos(-1.0) 21 22 typedef long long ll; 23 typedef unsigned long long ull; 24 typedef pair<int, int> pii; 25 int n, mod; 26 struct Matrix { ll det[4][4]; }; 27 Matrix ans, mat; 28 29 Matrix mul(Matrix x, Matrix y) { 30 Matrix ret; memset(ret.det, 0, sizeof(ret.det)); 31 for (int i = 0; i < 4; ++i) { 32 for (int k = 0; k < 4; ++k) { 33 if (x.det[i][k] == 0) { continue; } 34 for (int j = 0; j < 4; ++j) { 35 ret.det[i][j] = (ret.det[i][j] + x.det[i][k] * y.det[k][j]) % mod; 36 } 37 } 38 } 39 return ret; 40 } 41 void solve(ll x) { 42 while (x) { 43 if (x & 1) { ans = mul(mat, ans); } 44 mat = mul(mat, mat); x >>= 1; 45 } 46 } 47 48 int main() { 49 #ifdef __AiR_H 50 freopen("in.txt", "r", stdin); 51 // freopen("out.txt", "w", stdout); 52 #endif // __AiR_H 53 while (scanf("%d %d", &n, &mod) != EOF) { 54 if (n == 0) { printf("0 "); continue; } 55 if (n == 1) { printf("%d ", 2 % mod); continue; } 56 if (n == 2) { printf("%d ", 4 % mod); continue; } 57 if (n == 3) { printf("%d ", 6 % mod); continue; } 58 ans.det[0][0] = 6; ans.det[1][0] = 4; 59 ans.det[2][0] = 2; ans.det[3][0] = 1; 60 memset(mat.det, 0, sizeof(mat.det)); 61 mat.det[0][0] = mat.det[0][2] = mat.det[0][3] = 1; 62 mat.det[1][0] = mat.det[2][1] = mat.det[3][2] = 1; 63 solve(n - 3); printf("%d ", ans.det[0][0]); 64 } 65 return 0; 66 }
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <queue> 7 #include <vector> 8 #include <stack> 9 #include <map> 10 #include <set> 11 #include <cmath> 12 #include <cctype> 13 #include <ctime> 14 15 using namespace std; 16 17 #define REP(i, n) for (int i = 0; i < (n); ++i) 18 #define eps 1e-9 19 #define SZ(x) ((int)x.size()) 20 #define PI acos(-1.0) 21 22 typedef long long ll; 23 typedef unsigned long long ull; 24 typedef pair<int, int> pii; 25 struct Matrix { ll det[2][2]; }; 26 Matrix mat, ans; 27 int T, n, mod; 28 29 Matrix mul(Matrix x, Matrix y) { 30 Matrix ret; memset(ret.det, 0, sizeof(ret.det)); 31 for (int i = 0; i < 2; ++i) { 32 for (int k = 0; k < 2; ++k) { 33 if (x.det[i][k] == 0) { continue; } 34 for (int j = 0; j < 2; ++j) { 35 ret.det[i][j] = (ret.det[i][j] + x.det[i][k] * y.det[k][j]) % mod; 36 } 37 } 38 } 39 return ret; 40 } 41 void solve(ll x) { 42 while (x) { 43 if (x & 1) { ans = mul(mat, ans); } 44 mat = mul(mat, mat); x >>= 1; 45 } 46 } 47 48 int main() { 49 #ifdef __AiR_H 50 freopen("in.txt", "r", stdin); 51 // freopen("out.txt", "w", stdout); 52 #endif // __AiR_H 53 scanf("%d", &T); 54 while (T--) { 55 scanf("%d %d", &n, &mod); mat.det[1][1] = 2; 56 mat.det[0][0] = mat.det[0][1] = mat.det[1][0] = 1; 57 ans.det[0][0] = ans.det[1][1] = 1; 58 ans.det[0][1] = ans.det[1][0] = 0; 59 solve(n); printf("%lld ", ans.det[0][1]); 60 } 61 return 0; 62 }
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <queue> 7 #include <vector> 8 #include <stack> 9 #include <map> 10 #include <set> 11 #include <cmath> 12 #include <cctype> 13 #include <ctime> 14 15 using namespace std; 16 17 #define REP(i, n) for (int i = 0; i < (n); ++i) 18 #define eps 1e-9 19 #define SZ(x) ((int)x.size()) 20 #define PI acos(-1.0) 21 22 typedef long long ll; 23 typedef unsigned long long ull; 24 typedef pair<int, int> pii; 25 const int maxn = 40; 26 const ll mod = 1e4; 27 const double k = (sqrt(5.0) + 1.0) / 2.0; 28 int n; 29 int f[maxn]; 30 struct Matrix { ll det[4][4]; }; 31 Matrix ans_t, mat_t; 32 33 Matrix mul(Matrix x, Matrix y) { 34 Matrix ret; memset(ret.det, 0, sizeof(ret.det)); 35 for (int i = 0; i < 4; ++i) { 36 for (int k = 0; k < 4; ++k) { 37 if (x.det[i][k] == 0) { continue; } 38 for (int j = 0; j < 4; ++j) { 39 ret.det[i][j] = (ret.det[i][j] + x.det[i][k] * y.det[k][j]) % mod; 40 } 41 } 42 } 43 return ret; 44 } 45 void solve(ll x) { 46 while (x) { 47 if (x & 1) { ans_t = mul(mat_t, ans_t); } 48 mat_t = mul(mat_t, mat_t); x >>= 1; 49 } 50 } 51 52 int main() { 53 #ifdef __AiR_H 54 freopen("in.txt", "r", stdin); 55 // freopen("out.txt", "w", stdout); 56 #endif // __AiR_H 57 f[0] = 0; f[1] = 1; 58 for (int i = 2; i < maxn; ++i) { 59 f[i] = f[i - 1] + f[i - 2]; 60 } 61 while (scanf("%d", &n) != EOF) { 62 if (n < maxn) { printf("%d ", f[n]); continue; } 63 double ans = -0.5 * log10(5.0) + 1.0 * n * log10(k); 64 ans = ans - floor(ans); ans = pow(10.0, ans); 65 while (ans < 1000.0) { ans *= 10.0; } 66 printf("%d...", (int)ans); 67 ans_t.det[0][0] = 1; ans_t.det[1][0] = 0; 68 mat_t.det[0][0] = mat_t.det[0][1] = 1; 69 mat_t.det[1][0] = 1; mat_t.det[1][1] = 0; 70 solve(n - 1); printf("%04lld ", ans_t.det[0][0]); 71 } 72 return 0; 73 }
11 HDU 3306 Another kind of Fibonacci
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <queue> 7 #include <vector> 8 #include <stack> 9 #include <map> 10 #include <set> 11 #include <cmath> 12 #include <cctype> 13 #include <ctime> 14 15 using namespace std; 16 17 #define REP(i, n) for (int i = 0; i < (n); ++i) 18 #define eps 1e-9 19 #define SZ(x) ((int)x.size()) 20 #define PI acos(-1.0) 21 22 typedef long long ll; 23 typedef unsigned long long ull; 24 typedef pair<int, int> pii; 25 const ll mod = 1e4 + 7; 26 struct Matrix { ll det[4][4]; }; 27 Matrix mat, ans; 28 ll n, x, y; 29 30 Matrix mul(Matrix x, Matrix y) { 31 Matrix ret; memset(ret.det, 0, sizeof(ret.det)); 32 for (int i = 0; i < 4; ++i) { 33 for (int k = 0; k < 4; ++k) { 34 if (x.det[i][k] == 0) { continue; } 35 for (int j = 0; j < 4; ++j) { 36 ret.det[i][j] = (ret.det[i][j] + x.det[i][k] * y.det[k][j]) % mod; 37 } 38 } 39 } 40 return ret; 41 } 42 void solve(ll x) { 43 while (x) { 44 if (x & 1) { ans = mul(mat, ans); } 45 mat = mul(mat, mat); x >>= 1; 46 } 47 } 48 49 int main() { 50 #ifdef __AiR_H 51 freopen("in.txt", "r", stdin); 52 // freopen("out.txt", "w", stdout); 53 #endif // __AiR_H 54 while (scanf("%lld %lld %lld", &n, &x, &y) != EOF) { 55 memset(mat.det, 0, sizeof(mat.det)); x %= mod; y %= mod; 56 mat.det[0][0] = mat.det[2][1] = 1; 57 mat.det[0][1] = mat.det[1][1] = (x * x) % mod; 58 mat.det[0][2] = mat.det[1][2] = (y * y) % mod; 59 mat.det[0][3] = mat.det[1][3] = (2 * x * y) % mod; 60 mat.det[3][1] = x; mat.det[3][3] = y; 61 ans.det[0][0] = 2; 62 for (int i = 1; i < 4; ++i) { ans.det[i][0] = 1; } 63 solve(n - 1); printf("%lld ", ans.det[0][0]); 64 } 65 return 0; 66 }
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <queue> 7 #include <vector> 8 #include <stack> 9 #include <map> 10 #include <set> 11 #include <cmath> 12 #include <cctype> 13 #include <ctime> 14 #include <ext/rope> 15 16 using namespace std; 17 using namespace __gnu_cxx; 18 19 #define REP(i, n) for (int i = 0; i < (n); ++i) 20 #define eps 1e-9 21 #define SZ(x) ((int)x.size()) 22 #define PI acos(-1.0) 23 24 typedef long long ll; 25 typedef pair<int, int> pii; 26 27 struct Matrix { ll det[2][2]; }; 28 Matrix ans, mat; 29 ll a, b, n, mod; 30 31 Matrix mul(Matrix x, Matrix y) { 32 Matrix ret; memset(ret.det, 0, sizeof(ret.det)); 33 for (int i = 0; i < 2; ++i) { 34 for (int k = 0; k < 2; ++k) { 35 if (x.det[i][k] == 0) { continue; } 36 for (int j = 0; j < 2; ++j) { 37 ret.det[i][j] = (ret.det[i][j] + x.det[i][k] * y.det[k][j]) % mod; 38 } 39 } 40 } 41 return ret; 42 } 43 void solve(ll x) { 44 while (x) { 45 if (x & 1) { ans = mul(mat, ans); } 46 mat = mul(mat, mat); x >>= 1; 47 } 48 } 49 50 int main() { 51 #ifdef __AiR_H 52 freopen("in.txt", "r", stdin); 53 // freopen("out.txt", "w", stdout); 54 #endif // __AiR_H 55 while (scanf("%lld %lld %lld %lld", &a, &b, &n, &mod) != EOF) { 56 if (n == 1) { printf("%lld ", (2 * a) % mod); continue; } 57 ans.det[0][0] = a; ans.det[1][0] = 1; 58 mat.det[0][0] = a; mat.det[0][1] = b; 59 mat.det[1][0] = 1; mat.det[1][1] = a; 60 solve(n - 1); ans.det[0][0] *= 2; ans.det[0][0] %= mod; 61 printf("%d ", ans.det[0][0]); 62 } 63 return 0; 64 }
13 HDU 5950 Recursive sequence
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <queue> 7 #include <vector> 8 #include <stack> 9 #include <map> 10 #include <set> 11 #include <cmath> 12 #include <cctype> 13 #include <ctime> 14 #include <bitset> 15 16 using namespace std; 17 18 #define REP(i, n) for (int i = 0; i < (n); ++i) 19 #define eps 1e-9 20 21 typedef long long ll; 22 typedef pair<int, int> pii; 23 24 const int INF = 0x7fffffff; 25 struct Matrix { ll det[7][7]; }; 26 const ll mod = 2147493647; 27 Matrix mat, ans; 28 int T; 29 ll n, a, b; 30 31 Matrix mul(Matrix x, Matrix y) { 32 Matrix ret; memset(ret.det, 0, sizeof(ret.det)); 33 for (int i = 0; i < 7; ++i) { 34 for (int k = 0; k < 7; ++k) { 35 if (x.det[i][k] == 0) { continue; } 36 for (int j = 0; j < 7; ++j) { 37 ret.det[i][j] = (ret.det[i][j] + x.det[i][k] * y.det[k][j]) % mod; 38 } 39 } 40 } 41 return ret; 42 } 43 void solve(ll x) { 44 while (x) { 45 if (x & 1) { ans = mul(mat, ans); } 46 mat = mul(mat, mat); x >>= 1; 47 } 48 } 49 50 int main() { 51 #ifdef __AiR_H 52 freopen("in.txt", "r", stdin); 53 // freopen("out.txt", "w", stdout); 54 #endif // __AiR_H 55 scanf("%d", &T); 56 while (T--) { 57 scanf("%lld %lld %lld", &n, &a, &b); 58 if (n == 1) { printf("%lld ", a); continue; } 59 if (n == 2) { printf("%lld ", b); continue; } 60 ans.det[0][0] = b; ans.det[1][0] = a; ans.det[2][0] = 16; 61 ans.det[3][0] = 8; ans.det[4][0] = 4; ans.det[5][0] = 2; ans.det[6][0] = 1; 62 memset(mat.det, 0, sizeof(mat.det)); 63 mat.det[0][0] = 1; mat.det[0][1] = 2; mat.det[0][2] = 1; mat.det[0][3] = 4; 64 mat.det[0][4] = 6; mat.det[0][5] = 4; mat.det[0][6] = 1; mat.det[1][0] = 1; 65 mat.det[2][2] = 1; mat.det[2][3] = 4; mat.det[2][4] = 6; mat.det[2][5] = 4; 66 mat.det[2][6] = 1; mat.det[3][3] = 1; mat.det[3][4] = 3; mat.det[3][5] = 3; 67 mat.det[3][6] = 1; mat.det[4][4] = 1; mat.det[4][5] = 2; mat.det[4][6] = 1; 68 mat.det[5][5] = 1; mat.det[5][6] = 1; mat.det[6][6] = 1; 69 solve(n - 2); printf("%lld ", ans.det[0][0]); 70 } 71 return 0; 72 }
1 POJ 3223 Matrix Power Series
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <queue> 7 #include <vector> 8 #include <stack> 9 #include <map> 10 #include <set> 11 #include <cmath> 12 #include <cctype> 13 #include <ctime> 14 #include <bitset> 15 16 using namespace std; 17 18 #define REP(i, n) for (int i = 0; i < (n); ++i) 19 #define eps 1e-9 20 21 typedef long long ll; 22 typedef pair<int, int> pii; 23 24 const int INF = 0x7fffffff; 25 26 struct Matrix { ll det[60][60]; }; 27 int n, k, mod; 28 Matrix ans, mat; 29 30 Matrix mul(Matrix x, Matrix y) { 31 Matrix ret; memset(ret.det, 0, sizeof(ret.det)); 32 for (int i = 0; i < n; ++i) { 33 for (int k = 0; k < n; ++k) { 34 if (x.det[i][k] == 0) { continue; } 35 for (int j = 0; j < n; ++j) { 36 ret.det[i][j] = (ret.det[i][j] + x.det[i][k] * y.det[k][j]) % mod; 37 } 38 } 39 } 40 return ret; 41 } 42 void solve(ll x) { 43 while (x) { 44 if (x & 1) { ans = mul(ans, mat); } 45 mat = mul(mat, mat); x >>= 1; 46 } 47 } 48 49 int main() { 50 #ifdef __AiR_H 51 freopen("in.txt", "r", stdin); 52 // freopen("out.txt", "w", stdout); 53 #endif // __AiR_H 54 scanf("%d %d %d", &n, &k, &mod); 55 for (int i = 0; i < n; ++i) { 56 for (int j = 0; j < n; ++j) { scanf("%lld", &mat.det[i][j]); } 57 mat.det[i][n + i] = mat.det[n + i][n + i] = 1; 58 } 59 n *= 2; ++k; ans = mat; 60 solve(k - 1); n /= 2; 61 for (int i = 0; i < n; ++i) { 62 --ans.det[i][n + i]; 63 if (ans.det[i][n + i] < 0) { ans.det[i][n + i] += mod; } 64 } 65 for (int i = 0; i < n; ++i) { 66 for (int j = n; j < 2 * n - 1; ++j) { printf("%d ", ans.det[i][j]); } 67 printf("%d ", ans.det[i][2 * n - 1]); 68 } 69 return 0; 70 }
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <queue> 7 #include <vector> 8 #include <stack> 9 #include <map> 10 #include <set> 11 #include <cmath> 12 #include <cctype> 13 #include <ctime> 14 15 using namespace std; 16 17 #define REP(i, n) for (int i = 0; i < (n); ++i) 18 #define eps 1e-9 19 #define SZ(x) ((int)x.size()) 20 #define PI acos(-1.0) 21 22 typedef long long ll; 23 typedef unsigned long long ull; 24 typedef pair<int, int> pii; 25 const ll mod = 2009; 26 int n, Case = 0, T; 27 struct Matrix { ll det[4][4]; }; 28 Matrix ans, mat; 29 30 Matrix mul(Matrix x, Matrix y) { 31 Matrix ret; memset(ret.det, 0, sizeof(ret.det)); 32 for (int i = 0; i < 4; ++i) { 33 for (int k = 0; k < 4; ++k) { 34 if (x.det[i][k] == 0) { continue; } 35 for (int j = 0; j < 4; ++j) { 36 ret.det[i][j] = (ret.det[i][j] + x.det[i][k] * y.det[k][j]) % mod; 37 } 38 } 39 } 40 return ret; 41 } 42 void solve(ll x) { 43 while (x) { 44 if (x & 1) { ans = mul(mat, ans); } 45 mat = mul(mat, mat); x >>= 1; 46 } 47 } 48 49 int main() { 50 #ifdef __AiR_H 51 freopen("in.txt", "r", stdin); 52 // freopen("out.txt", "w", stdout); 53 #endif // __AiR_H 54 scanf("%d", &T); 55 while (T--) { 56 scanf("%d", &n); printf("Case %d: ", ++Case); 57 if (n == 0) { printf("1 "); continue; } 58 if (n == 1) { printf("4 "); continue; } 59 if (n == 2) { printf("9 "); continue; } 60 ans.det[0][0] = 9; ans.det[1][0] = 5; 61 ans.det[2][0] = 3; ans.det[3][0] = 1; 62 memset(mat.det, 0, sizeof(mat.det)); 63 mat.det[0][0] = mat.det[2][1] = mat.det[3][2] = 1; 64 mat.det[0][1] = mat.det[1][1] = 3; 65 mat.det[0][2] = mat.det[1][2] = 2; 66 mat.det[0][3] = mat.det[1][3] = 7; 67 solve(n - 2); printf("%lld ", ans.det[0][0]); 68 } 69 return 0; 70 }
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <queue> 7 #include <vector> 8 #include <stack> 9 #include <map> 10 #include <set> 11 #include <cmath> 12 #include <cctype> 13 #include <ctime> 14 15 using namespace std; 16 17 #define REP(i, n) for (int i = 0; i < (n); ++i) 18 #define eps 1e-9 19 #define SZ(x) ((int)x.size()) 20 #define PI acos(-1.0) 21 22 typedef long long ll; 23 typedef unsigned long long ull; 24 typedef pair<int, int> pii; 25 const int maxn = 110; 26 struct Matrix { ll det[100][100]; }; 27 Matrix mat, unit; 28 int T, n, m, l, r, mod; 29 ll ans[maxn], a[maxn]; 30 31 Matrix mul(Matrix x, Matrix y) { 32 Matrix ret; memset(ret.det, 0, sizeof(ret.det)); 33 for (int k = 0; k < n; ++k) { 34 for (int j = 0; j < n; ++j) { 35 ret.det[0][j] = (ret.det[0][j] + x.det[0][k] * y.det[k][j]) % mod; 36 } 37 } 38 for (int i = 1; i < n; ++i) { 39 ret.det[i][0] = ret.det[i - 1][n - 1]; 40 for (int j = 1; j < n; ++j) { 41 ret.det[i][j] = ret.det[i - 1][j - 1]; 42 } 43 } 44 return ret; 45 } 46 void solve(ll x) { 47 while (x) { 48 if (x & 1) { unit = mul(mat, unit); } 49 mat = mul(mat, mat); x >>= 1; 50 } 51 } 52 53 int main() { 54 #ifdef __AiR_H 55 freopen("in.txt", "r", stdin); 56 // freopen("out.txt", "w", stdout); 57 #endif // __AiR_H 58 scanf("%d", &T); 59 while (T--) { 60 scanf("%d %d %d %d %d", &n, &m, &l, &r, &mod); 61 for (int i = 0; i < n; ++i) { scanf("%lld", &a[i]); } 62 memset(unit.det, 0, sizeof(unit.det)); 63 for (int i = 0; i < n; ++i) { unit.det[i][i] = 1; } 64 memset(mat.det, 0, sizeof(mat.det)); 65 for (int i = 0; i < n; ++i) { 66 mat.det[i][i] = 1; 67 mat.det[i][(i + n - 1) % n] = r; 68 mat.det[i][(i + 1) % n] = l; 69 } 70 solve(m); memset(ans, 0, sizeof(ans)); 71 for (int i = 0; i < n; ++i) { 72 for (int j = 0; j < n; ++j) { 73 ans[i] += a[j] * unit.det[i][j]; ans[i] %= mod; 74 } 75 } 76 for (int i = 0; i < n; ++i) { 77 printf(i == n - 1 ? "%lld " : "%lld ", ans[i]); 78 } 79 } 80 return 0; 81 }
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <queue> 7 #include <vector> 8 #include <stack> 9 #include <map> 10 #include <set> 11 #include <cmath> 12 #include <cctype> 13 #include <ctime> 14 15 using namespace std; 16 17 #define REP(i, n) for (int i = 0; i < (n); ++i) 18 #define eps 1e-9 19 #define SZ(x) ((int)x.size()) 20 #define PI acos(-1.0) 21 22 typedef long long ll; 23 typedef unsigned long long ull; 24 typedef pair<int, int> pii; 25 const ll mod = 1e9 + 7; 26 struct Matrix { ll det[2][2]; }; 27 Matrix mat, ans; 28 ll n; 29 30 Matrix mul(Matrix x, Matrix y) { 31 Matrix ret; memset(ret.det, 0, sizeof(ret.det)); 32 for (int i = 0; i < 2; ++i) { 33 for (int k = 0; k < 2; ++k) { 34 if (x.det[i][k] == 0) { continue; } 35 for (int j = 0; j < 2; ++j) { 36 ret.det[i][j] = (ret.det[i][j] + x.det[i][k] * y.det[k][j]) % mod; 37 } 38 } 39 } 40 return ret; 41 } 42 void solve(ll x) { 43 while (x) { 44 if (x & 1) { ans = mul(mat, ans); } 45 mat = mul(mat, mat); x >>= 1; 46 } 47 } 48 49 int main() { 50 #ifdef __AiR_H 51 freopen("in.txt", "r", stdin); 52 // freopen("out.txt", "w", stdout); 53 #endif // __AiR_H 54 mat.det[0][0] = mat.det[1][1] = 3; 55 mat.det[0][1] = mat.det[1][0] = 1; 56 ans.det[0][0] = 1; scanf("%lld", &n); 57 solve(n); printf("%lld ", ans.det[0][0]); 58 return 0; 59 }
2 Codeforces 450B Jzzhu and Sequences
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <queue> 7 #include <vector> 8 #include <stack> 9 #include <map> 10 #include <set> 11 #include <cmath> 12 #include <cctype> 13 #include <ctime> 14 15 using namespace std; 16 17 #define REP(i, n) for (int i = 0; i < (n); ++i) 18 #define eps 1e-9 19 #define SZ(x) ((int)x.size()) 20 #define PI acos(-1.0) 21 22 typedef long long ll; 23 typedef unsigned long long ull; 24 typedef pair<int, int> pii; 25 const ll mod = 1e9 + 7; 26 struct Matrix { ll det[2][2]; }; 27 Matrix ans, mat; 28 ll n, x, y; 29 30 Matrix mul(Matrix x, Matrix y) { 31 Matrix ret; memset(ret.det, 0, sizeof(ret.det)); 32 for (int i = 0; i < 2; ++i) { 33 for (int k = 0; k < 2; ++k) { 34 if (x.det[i][k] == 0) { continue; } 35 for (int j = 0; j < 2; ++j) { 36 ret.det[i][j] = (ret.det[i][j] + x.det[i][k] * y.det[k][j]) % mod; 37 } 38 } 39 } 40 return ret; 41 } 42 void solve(ll x) { 43 while (x) { 44 if (x & 1) { ans = mul(mat, ans); } 45 mat = mul(mat, mat); x >>= 1; 46 } 47 } 48 49 int main() { 50 #ifdef __AiR_H 51 freopen("in.txt", "r", stdin); 52 // freopen("out.txt", "w", stdout); 53 #endif // __AiR_H 54 scanf("%lld %lld %lld", &x, &y, &n); 55 x = (x + mod) % mod; y = (y + mod) % mod; 56 if (n == 1) { printf("%lld ", x); return 0; } 57 if (n == 2) { printf("%lld ", y); return 0; } 58 ans.det[0][0] = y; ans.det[1][0] = x; 59 mat.det[0][0] = mat.det[1][0] = 1; 60 mat.det[0][1] = -1; 61 solve(n - 2); if (ans.det[0][0] < 0) { ans.det[0][0] += mod; } 62 printf("%lld ", ans.det[0][0]); 63 return 0; 64 }
3 Codeforces 691E Xor-sequences
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <queue> 7 #include <vector> 8 #include <stack> 9 #include <map> 10 #include <set> 11 #include <cmath> 12 #include <cctype> 13 #include <ctime> 14 15 using namespace std; 16 17 #define REP(i, n) for (int i = 0; i < (n); ++i) 18 #define eps 1e-9 19 #define SZ(x) ((int)x.size()) 20 #define PI acos(-1.0) 21 22 typedef long long ll; 23 typedef unsigned long long ull; 24 typedef pair<int, int> pii; 25 const ll mod = 1e9 + 7; 26 const int maxn = 110; 27 struct Matrix { ll det[100][100]; }; 28 Matrix ans, mat; 29 int n; 30 ll k; 31 ll a[maxn]; 32 int cnt[maxn]; 33 34 Matrix mul(Matrix x, Matrix y) { 35 Matrix ret; memset(ret.det, 0, sizeof(ret.det)); 36 for (int i = 0; i < n; ++i) { 37 for (int k = 0; k < n; ++k) { 38 if (x.det[i][k] == 0) { continue; } 39 for (int j = 0; j < n; ++j) { 40 ret.det[i][j] = (ret.det[i][j] + x.det[i][k] * y.det[k][j]) % mod; 41 } 42 } 43 } 44 return ret; 45 } 46 void solve(ll x) { 47 while (x) { 48 if (x & 1) { ans = mul(mat, ans); } 49 mat = mul(mat, mat); x >>= 1; 50 } 51 } 52 53 int main() { 54 #ifdef __AiR_H 55 freopen("in.txt", "r", stdin); 56 // freopen("out.txt", "w", stdout); 57 #endif // __AiR_H 58 scanf("%d %lld", &n, &k); 59 for (int i = 0; i < n; ++i) { scanf("%lld", &a[i]); } 60 for (int i = 0; i < n; ++i) { 61 for (int j = 0; j < n; ++j) { 62 if (__builtin_popcountll(a[i] ^ a[j]) % 3 == 0) { mat.det[i][j] = 1; ++cnt[i]; } 63 } 64 } 65 for (int i = 0; i < n; ++i) { ans.det[i][0] = 1; } 66 solve(k - 1); ll ret = 0; 67 for (int i = 0; i < n; ++i) { ret += ans.det[i][0]; ret %= mod; } 68 printf("%lld ", ret); 69 return 0; 70 }
4 Codeforces 852B Neural Network country
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <queue> 7 #include <vector> 8 #include <stack> 9 #include <map> 10 #include <set> 11 #include <cmath> 12 #include <cctype> 13 #include <ctime> 14 15 using namespace std; 16 17 #define REP(i, n) for (int i = 0; i < (n); ++i) 18 #define eps 1e-9 19 #define SZ(x) ((int)x.size()) 20 #define PI acos(-1.0) 21 22 typedef long long ll; 23 typedef unsigned long long ull; 24 typedef pair<int, int> pii; 25 const ll mod = 1e9 + 7; 26 const int maxn = 1e6 + 10; 27 struct Matrix { ll det[100][100]; }; 28 int n, l, m; 29 Matrix ans, mat; 30 int cnt[maxn], a[3][maxn]; 31 32 Matrix mul(Matrix x, Matrix y) { 33 Matrix ret; memset(ret.det, 0, sizeof(ret.det)); 34 for (int i = 0; i < m; ++i) { 35 for (int k = 0; k < m; ++k) { 36 if (x.det[i][k] == 0) { continue; } 37 for (int j = 0; j < m; ++j) { 38 ret.det[i][j] = (ret.det[i][j] + x.det[i][k] * y.det[k][j]) % mod; 39 } 40 } 41 } 42 return ret; 43 } 44 void solve(ll x) { 45 while (x) { 46 if (x & 1) { ans = mul(mat, ans); } 47 mat = mul(mat, mat); x >>= 1; 48 } 49 } 50 void cal() { 51 memset(mat.det, 0, sizeof(mat.det)); 52 for (int i = 0; i < m; ++i) { 53 for (int j = 0; j < m; ++j) { 54 mat.det[i][j] = cnt[(m + i - j) % m]; 55 } 56 } 57 } 58 59 int main() { 60 #ifdef __AiR_H 61 freopen("in.txt", "r", stdin); 62 // freopen("out.txt", "w", stdout); 63 #endif // __AiR_H 64 scanf("%d %d %d", &n, &l, &m); 65 for (int i = 0; i < 3; ++i) { 66 for (int j = 0; j < n; ++j) { scanf("%d", &a[i][j]); } 67 } 68 memset(cnt, 0, sizeof(cnt)); 69 for (int i = 0; i < n; ++i) { ++cnt[a[0][i]]; } 70 for (int i = 0; i < m; ++i) { ans.det[i][0] = cnt[(i + 1) % m]; } 71 memset(cnt, 0, sizeof(cnt)); 72 for (int i = 0; i < n; ++i) { ++cnt[a[1][i]]; } cal(); 73 solve(l - 2); memset(cnt, 0, sizeof(cnt)); 74 for (int i = 0; i < n; ++i) { ++cnt[(a[1][i] + a[2][i]) % m]; } 75 cal(); ans = mul(mat, ans); printf("%lld ", ans.det[m - 1][0]); 76 return 0; 77 }