OI题解 - GuGu Convolution

不得不说,读懂题就花了不少时间……

最后发现它说了这么多就是为了解释它让我们求的式子的来源……


· 题目

对于数列 $A=(a_0,a_1,a_2,…)$ ,定义:

对于实数 $c$,我们根据它定义数列:

给定正整数 $A,B,n$ ;根据 $A$ 构造数列 $U_A$(记 $U_A$ 中的元素为 $u_i$),根据 $B$ 构造数列 $E_\sqrt{B}$(记 $E_\sqrt B$ 中的元素为 $e_i$);求:

输出时,第一行输出 $q$,接下来 $q$ 行,每行输出整数 $a_i,b_i$;表示答案为 $\sum_{i=1}^qa^i\sqrt {b_i}$。


· 解析

根据题目我们可以知道:

那么可以知道:

因为对于任何实数 $x$ ,满足:

所以我们可以得到(理解一下,可能需要思考~):

再继续推导:

把上面这个式子先留着(上面的这个式子是我们要求的答案);我们先来看另一个式子的推导:

$(a+b\sqrt t)(c+d\sqrt t)=(ac+bdt)+(ad+bc)\sqrt t$ ($a,b,c,d,t$ 均为常数)

知道这个等式有什么用呢?

可以发现形如 $(a+b\sqrt t)$ 的两个式子相乘,我们仍可以得到一个形如 $(a+b\sqrt t)$ 的式子,于是…… $(A+\sqrt B)^n$ 和 $(A-\sqrt B)^n$ 展开后也会得到形如 $(a+b\sqrt t)$ 的式子。

多项式的幂?式子的形式相同?——快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ll SQPow(ll fir,ll sec,ll thi,ll B,ll mod){ //求 (fir+sec*\sqrt(B))^thi % mod
ll resfir=1,ressec=0; //返回值是 resfir+ressec*\sqrt(B)
while(thi){
if(thi&1){
ll _resfir,_ressec;
_resfir=(resfir*fir%mod+ressec*sec%mod*B%mod)%mod;
_ressec=(ressec*fir%mod+resfir*sec%mod)%mod;
resfir=_resfir;ressec=_ressec;
//根据上面推导的式子更新返回值
}
ll _fir,_sec;
_fir=(sec*sec%mod*B%mod+fir*fir%mod)%mod;
_sec=fir*sec%mod*2%mod;
fir=_fir;sec=_sec;
thi>>=1;
}
return ressec; //这里只返回 a+b\sqrt(B) 中的 b,原因下面解释
}

令 $(A+\sqrt B)^n=P_1+Q_1\sqrt B, (A-\sqrt B)=P_2+Q_2\sqrt B$ ($P_1,P_2,Q_1,Q_2$是常数);

可以发现 $P_1=P_2=A^n+A^{n-2}B+A^{n-4}B^2…$ ,所以 $(A+\sqrt B)^n-(A-\sqrt B)^n=(Q_1-Q_2)\sqrt B$ ;那么答案就是:

可见要将上式表示为 $\sum_{i=1}^qa_i\sqrt {b_i}$ 的形式 —— 令 $B=x^2y(x是尽可能大的正整数)$,则 $q=1,a_1=(Q_1-Q_2)x,b_1=y$ 。(别忘了分解质因数


· 源代码

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll A,B,n,P;
int prm[1005],nprm;
bool vis[1005];
//(fir+sec*sqrt(B))^thi
ll SQPow(ll fir,ll sec,ll thi,ll B,ll mod){
ll resfir=1,ressec=0;
while(thi){
if(thi&1){
ll _resfir,_ressec;
_resfir=(resfir*fir%mod+ressec*sec%mod*B%mod)%mod;
_ressec=(ressec*fir%mod+resfir*sec%mod)%mod;
resfir=_resfir;ressec=_ressec;
}
ll _fir,_sec;
_fir=(sec*sec%mod*B%mod+fir*fir%mod)%mod;
_sec=fir*sec%mod*2%mod;
fir=_fir;sec=_sec;
thi>>=1;
}
return ressec;
}
ll QPow(ll under,ll over,ll mod){
ll res=1;
while(over){
if(over&1) res=res*under%mod;
under=under*under%mod;
over>>=1;
}
return res;
}
ll Primnum(ll num){
ll ret=1;
for(int i=1;i<=nprm;i++){
int cnt=1;
while(num%prm[i]==0){
num/=prm[i];
cnt++;
if(cnt&1) ret*=prm[i];
}
}
return ret;
}
void Process(){
int lim=1000;
for(int i=2;i<=lim;i++){
if(!vis[i]) prm[++nprm]=i;
for(int j=1;i*prm[j]<=lim && j<=nprm;j++){
vis[i*prm[j]]=true;
if(i%prm[j]==0) break;
}
}
}
int main(){
Process();
int ncase;scanf("%d",&ncase);
while(ncase--){
scanf("%lld%lld%lld%lld",&A,&B,&n,&P);
ll res1=SQPow(A,1,n,B,P*2),res2=SQPow(A,-1,n,B,P*2);
ll prtsec,delta=Primnum(B);
prtsec=(res1-res2+P*2)%(P*2)/2;
prtsec=prtsec*delta%P;
B=B/delta/delta;
printf("1 %lld %lld\n",prtsec,B);
}
return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com ,欢迎提问~

0%