这个题。。。
1 #include <bits/stdc++.h> 2 #define rep(i, a, b) for (int i = a; i <= b; i++) 3 #define drep(i, a, b) for (int i = a; i >= b; i--) 4 #define REP(i, a, b) for (int i = a; i < b; i++) 5 #define mp make_pair 6 #define pb push_back 7 #define clr(x) memset(x, 0, sizeof(x)) 8 #define xx first #define yy second 9 using namespace std; 10 typedef pair<int, int> pii; 11 typedef unsigned long long ll; 12 const int inf = 0x3f3f3f3f; 13 const ll INF = 0x3f3f3f3f3f3f3f3fll; 14 //************************************************ 15 16 const ll mod = 7528443412579576937LL; 17 ll mul(ll base, ll num) { 18 ll ret(0); 19 while (num) { 20 if (num & 1) ret = (ret + base) % mod; 21 base = (base + base) % mod; 22 num >>= 1; 23 } 24 return ret; 25 } 26 struct matrix { 27 ll s[3][3]; matrix () { clr(s); } 28 matrix operator * (const matrix &B) const { 29 matrix A = *this, C; 30 rep(i, 1, 2) rep(j, 1, 2) rep(k, 1, 2) 31 C.s[i][j] = (C.s[i][j] + mul(A.s[i][k], B.s[k][j]) % mod) % mod; 32 return C; 33 } 34 } ori; 35 36 matrix POW(matrix base, ll num) { 37 matrix ret = ori; 38 while (num) { 39 if (num & 1) ret = ret * base; 40 base = base * base; 41 num >>= 1; 42 } 43 return ret; 44 } 45 46 int main() { 47 ll b, d, n; scanf("%llu%llu%llu", &b, &d, &n); 48 ll a = b, c = (d - b * b) >> 2; 49 ori.s[1][1] = ori.s[2][2] = 1; 50 matrix base; base.s[1][1] = a, base.s[2][1] = c, base.s[1][2] = 1; 51 matrix ans; 52 ans.s[1][2] = 2, ans.s[1][1] = b; 53 ans = ans * POW(base, n); 54 if (d != b * b && n % 2 == 0) ans.s[1][2]--; 55 printf("%llu ", ans.s[1][2]); 56 }