ComentOJ-C72-4033 「火鼠的皮衣 -不焦躁的内心-」
给定 $math_inline$n, a, b, p$math_inline$ （p不一定是质数），求 $math_inline$\sum\limits_{i=0}^{\lfloor\frac{n}{2}\rfloor} a^i b^{n-2i} {n\choose 2i}$math_inline$ 对 $math_inline$p$math_inline$ 取模的结果，T组询问。
首先对求和公式进行转化；
$math_inline$ \begin{equation} \begin{aligned} ans &= \sum\limits_{i=0}^{\lfloor\frac{n}{2}\rfloor} a^i b^{n-2i} {n\choose 2i} \\ &= \sum\limits_{i=0}^{n}(\sqrt{a})^ib^{n-i}{n \choose i}\left[i\%2==0\right] \end{aligned} \end{equation} $math_inline$考虑把 $math_inline$\left[i\%2==0\right]$math_inline$ 改写成 $math_inline$\frac{1^i + {(-1)}^i}{2}$math_inline$
$math_inline$ \begin{equation} \begin{aligned} ans &= \sum\limits_{i=0}^{n}(\sqrt{a})^ib^{n-i}{n \choose i}\left[i\%2==0\right] \\ &= \sum\limits_{i=0}^{n}(\sqrt{a})^ib^{n-i}{n \choose i}\frac{1^i + {(-1)}^i}{2} \\ &= \frac{1}{2}\left(\sum\limits_{i=0}^{n}(\sqrt{a})^ib^{n-i}{n \choose i} + \sum\limits_{i=0}^{n}(-\sqrt{a})^ib^{n-i}{n \choose i}\right) \end{aligned} \end{equation} $math_inline$根据二项式定理 $math_inline${(a+b)}^n=\sum\limits^n_{k=0}{n \choose k}x^{n-k}y^k=\sum\limits^n_{k=0}{n \choose k}x^ky^{n-k}$math_inline$
$math_inline$ \begin{equation} \begin{aligned} ans &= \frac{1}{2}\left(\left(b+\sqrt{a}\right)^n+\left(b-\sqrt{a}\right)^n\right) \end{aligned} \end{equation} $math_inline$因为 a,b 固定，可以设 Fx 为当 n=x 时的答案，那么 Fx 一定是满足一个二项递推式，即 $math_inline$Fx=A\times F_{x-1}+B\times F_{x-2}$math_inline$ 。因为 a 不一定有二次剩余，所以不能用快速幂来做，p也不一定是质数，所以不能用 BM 算法求出 A,B（有一个求逆元的步骤）。不过可以通过手算 $math_inline$F_0,F_1,F_2,F_3$math_inline$ 然后解一个二元一次方程组来算出 A,B。
$math_inline$ \begin{aligned} F_0 &= 1 \\ F_1 &= b \\ F_2 &= b^2+a \\ F_3 &= b^3+3ab \end{aligned} $math_inline$或者
考虑特征根方程： $math_inline$x^2=Ax+B$math_inline$ ，即 $math_inline$x^2-Ax-B=0$math_inline$ ，方程的两个解理应为答案式子中的两个特征根 $math_inline$b+\sqrt{a},b-\sqrt{a}$math_inline$ 。根据韦达定理，可知 A 为两根之和 $math_inline$(b+\sqrt{a})+(b-\sqrt{a})=2b$math_inline$ ，-B 为两根之积，即 $math_inline$B=-(b+\sqrt{a})(b-\sqrt{a})=a-b^2$math_inline$ 。那么求出 $math_inline$F_0=1, F_1=b$math_inline$ 之后用矩阵乘法就可以在 $math_inline$O(log(n))$math_inline$ 的时间内求出。
矩阵为
$math_inline$ \left ( \begin{matrix} 1 & b \end{matrix} \right ) \left ( \begin{matrix} 0 & a-b^2 \\ 1 & 2b \end{matrix} \right ) $math_inline$或
$math_inline$ \left ( \begin{matrix} b & 1 \end{matrix} \right ) \left ( \begin{matrix} 2b & 1 \\ a-b^2 & 0 \end{matrix} \right ) $math_inline$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;
}
ASE
Code 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