ComentOJ-C72-4033 「火鼠的皮衣 -不焦躁的内心-
给定
首先对求和公式进行转化；
考虑把
根据二项式定理
因为 a,b 固定，可以设 Fx 为当 n=x 时的答案，那么 Fx 一定是满足一个二项递推式，即
或者
考虑特征根方程：
矩阵为
或
Code 1
/* ***********************************************
Author : Akvicor
Created Time : Mon Oct 28 14:54:35 2019
File Name : D.cpp
************************************************ */
#include <bits/stdc++.h>
#define FAST_IO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ASB using namespace std; typedef long long ll; namespace AkvicorS {
#define ASE } int main() { return AkvicorS::sol(); }
ASB
int t;
ll n, a, b, p;
inline ll mul(ll x, ll y){ return (__int128)x*y%p; }
struct Mat{
int r, c;
ll num[2][2];
Mat(int _r=2, int _c=2){r=_r;c=_c;}
Mat operator * (const Mat &obj) const{
Mat res(r, obj.c);
for(int i = 0; i < res.r; ++i){
for(int j = 0; j < res.c; ++j){
res.num[i][j] = 0;
for(int k = 0; k < c; ++k){
res.num[i][j] = (res.num[i][j] + mul(num[i][k], obj.num[k][j]))%p;
}
}
}
return res;
}
}f, g;
int sol(){
FAST_IO;
cin >> t;
while(t--){
cin >> n >> a >> b >> p;
a %= p; b %= p;
f.r = 1;
f.c = g.r = g.c = 2;
f.num[0][0] = 1; f.num[0][1] = b;
g.num[0][0] = 0; g.num[0][1] = (a+p-mul(b, b)) % p;
g.num[1][0] = 1; g.num[1][1] = 2*b%p;
for(; n; n >>= 1, g = g*g) if(n&1) f = f*g;
cout << f.num[0][0] << endl;
}
return 0;
}
ASECode 2
/* ***********************************************
Author : Akvicor
Created Time : Mon Oct 28 14:54:35 2019
File Name : D.cpp
************************************************ */
#include <bits/stdc++.h>
#define FAST_IO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ASB using namespace std; typedef long long ll; namespace AkvicorS {
#define ASE } int main() { return AkvicorS::sol(); }
ASB
int t;
ll n, a, b, p;
typedef pair<ll, ll> pll;
#define fi first
#define se second
ll mul(ll x, ll y){ return (__int128)x*y%p; }
pll operator * (pll a, pll b){
return make_pair( ( mul(a.fi, b.fi) + mul( mul(a.se, b.se), ::AkvicorS::a) ) % p, ( mul(a.se, b.fi) + mul(a.fi, b.se) ) % p);
}
pll qpow(pll x, ll y){
pll ans = make_pair(1, 0);
for(; y; y>>=1, x=x*x) if(y&1) ans = ans * x;
return ans;
}
int sol(){
FAST_IO;
cin >> t;
while(t--){
cin >> n >> a >> b >> p;
cout << qpow(make_pair(b, 1), n).fi << endl;
}
return 0;
}
ASE