Comet OJ Contest #13 D
$\displaystyle \sum_{i=0}^{\left\lfloor\frac{n}{2}\right\rfloor} a^{i} b^{n-2 i}\left(\begin{array}{c}{n} \\ {2 i}\end{array}\right)$
$T \leq 10^4 , n , m , p \leq 10^{18}$
注意，由于$p$不一定是质数，而且数据范围看起来很快速幂所有貌似只能快速幂。
这个式子可以化成：
$\displaystyle \sum_{i=0}^{\left\lfloor\frac{n}{2}\right\rfloor} {\sqrt a}^{2i} b^{n-2 i}\left(\begin{array}{c}{n} \\ {2 i}\end{array}\right)$
然后其实就是$(\sqrt a + b)^n$的偶数次项的和。
偶数次项其实可以化成$\frac{1}{2} ( (\sqrt a + b)^n - (\sqrt a - b) ^ n )$ 当然这是当$n$为偶数时，如果是奇数要反过来。
这个式子可以直接类似复数的快速幂，因为我们知道最后一定不会剩下根号。
当然，也可以看成一个特征方程的根，就是一个$f(1) = 1 , f(2) = b , f(n) = 2bf(n - 1) + (-b^2+a) f(n - 2)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
#define int __int128_t
#define ll __int128_t
#define N 2
struct mtrx{
ll a[3][3];
} tmp , cur , ans ;
ll a , b , P;
void mul( mtrx& a , mtrx& b ) {
memset(tmp.a,0,sizeof tmp.a);
for( ll i = 0 ; i < N ; ++ i )
for( ll p = 0 ; p < N ; ++ p )
if(a.a[i][p])
for( ll j = 0 ; j < N ; ++ j )
tmp.a[i][j] += a.a[i][p] * b.a[p][j] , tmp.a[i][j] %= P;
}
void power( ll n ) {
memset(cur.a , 0 , sizeof cur.a) , memset(ans.a,0,sizeof ans.a);
cur.a[0][0] = 2 * b % P , cur.a[0][1] = ( - b * b % P + a + P ) % P;
cur.a[1][0] = 1;
ans.a[0][0] = 1, ans.a[1][1] = 1;
while( n ) {
if( n & 1 ) mul( ans , cur ) , ans = tmp;
mul( cur , cur ) , cur = tmp , n >>= 1 ;
}
}
ll n;
inline __int128_t read()
{
int X=0,w=0; char ch=0;
while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
return w?-X:X;
}
inline void print(__int128_t x)
{
if(x<0){putchar('-');x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
signed main() {
signed T; cin >> T;
while( T-- ){
n = read() , a = read() , b = read( ) , P = read();
power(n - 1);
print((ans.a[0][0] * b % P + ans.a[0][1]) % P); puts("");
}
}
|
