题目地址 https://cometoj.com/contest/72/problem/%EF%BC%A4
给定a,b,c,p,范围1e18，求
$$\sum_{i=0}^{n/2}{a^i b^{n-2i} C(n,2i)}$$
把n/2用n代换，则a化为\(\sqrt{a}^i\)，b化为\(b^{n-i}\)。对这些偶数项求和，相当于乘\((1^i+(-1)^i)/2\)。根据二项式定理，可化简为
$$ans=\frac{1}{2} ((\sqrt{a}+b)^n + (\sqrt{a}-b)^n)$$
然后就是快速算这个算式。由于p是任意数，不能用二次剩余。万金油BM线性递推也不能用(需要逆元)。这是一个二阶线性递推，一种方法是算前几项，暴力解出递推系数。更数学的方法是，上式已知特征方程的解，所以用韦达定理立即得到方程系数，然后套矩阵快速幂。
然后一种更便捷的方法 ，直接对根式快速幂。注意到这里要对答案除个2，用$$\frac{a}{2} mod p=\frac{a mod (2p)}{2}$$即可。
/*Author: fffasttimeDate:*/#include <bits/stdc++.h>using namespace std;
typedef long long ll;
#define inc(i,n) for (int i=0;i<n;i++)const int N=100010;
typedef __int128 lll;
ll p;ll n, a, b;ll mul(ll x,ll y){
ll t=(x*y-(ll)((long double)x/p*y+0.5)*p);
return t<0 ? t+p : t;
}struct Sq{
ll x, y;Sq operator*(const Sq &v) const{
return {(mul(x,v.x)+mul(mul(y,v.y),a))%p,(mul(x,v.y)+mul(y,v.x))%p};
}void prt(){printf("%lld %lld\n",x,y);}
};
Sq qpow(Sq s, ll x){
Sq ans={1,0};
for(;x;s=s*s,x>>=1)
if (x&1) ans=ans*s;
return ans;
}int main(){
int T; cin>>T;
while (T--){
scanf("%lld%lld%lld%lld",&n,&a,&b,&p);
p*=2;
Sq ans1=qpow({b%p,1},n);
Sq ans2=qpow({b%p,p-1},n);
//ans1.prt(); ans2.prt();printf("%lld\n",(ans1.x+ans2.x)%p/2);
}return 0;
}