hdu 4565So Easy!
公式推导：( a + b ^ 0.5 ) ^ n + ( a - b ^ 0.5 ) ^ n = Ck, Ck * ( ( a + b ^ 0.5 ) + ( a - b ^ 0.5 ) ) = ( ( a + b ^ 0.5 ) + ( a - b ^ 0.5 ) ) * ( a + b ^ 0.5 ) ^ n + ( a - b ^ 0.5 ) ^ n => 2 * a * Ck = Ck+1 + (a * a - b) * Ck-1 => Ck+1 + Ck = Ck * (2 * a + 1 ) + (a * a - b) * Ck-1 ==> Ck + 1 = 2 * a b - a * a * Ck Ck 1 0 Ck -1==> Ck + 1 = 2 * a b - a * a ^ n * 2 * a Ck 1 0 2//#pragma comment(linker, "/STACK:102400000,102400000")#include <cstdio>#define LL long longLL s[2], m;struct node {LL arr[2][2];};node power(node p, int pos){if(pos == 1) return p;node v = power(p, pos / 2);node q;q.arr[0][0] = (v.arr[0][0] * v.arr[0][0] + v.arr[0][1] * v.arr[1][0]) % m;q.arr[0][1] = (v.arr[0][0] * v.arr[0][1] + v.arr[0][1] * v.arr[1][1]) % m;q.arr[1][0] = (v.arr[1][0] * v.arr[0][0] + v.arr[1][1] * v.arr[1][0]) % m;q.arr[1][1] = (v.arr[1][0] * v.arr[0][1] + v.arr[1][1] * v.arr[1][1]) % m;if(pos % 2 == 0) return q;v.arr[0][0] = (q.arr[0][0] * p.arr[0][0] + q.arr[0][1] * p.arr[1][0]) % m;v.arr[0][1] = (q.arr[0][0] * p.arr[0][1] + q.arr[0][1] * p.arr[1][1]) % m;v.arr[1][0] = (q.arr[1][0] * p.arr[0][0] + q.arr[1][1] * p.arr[1][0]) % m;v.arr[1][1] = (q.arr[1][0] * p.arr[0][1] + q.arr[1][1] * p.arr[1][1]) % m;return v;}int main(){ // freopen("in.txt", "r", stdin); LL a, b; int n; while (scanf("%I64d %I64d %d %I64d", &a, &b, &n, &m) != EOF){ if(n == 1){ printf("%lld\n", a * 2 % m); continue; } s[0] = 2 * a % m, s[1] = 2; node p; p.arr[0][0] = a * 2 % m; p.arr[0][1] = (b - a * a) % m; p.arr[1][0] = 1, p.arr[1][1] = 0; node q = p; q = power(p, n - 1); printf("%I64d\n", (q.arr[0][0] * s[0] % m + q.arr[0][1] * s[1] % m + m * 2) % m); } return 0;}