JLOI 2015 有意义的字符串（矩阵乘法）

发表于 |
字数统计: 1,012字 | 阅读时长 ≈ 5min

[JLOI2015 DAY1]有意义的字符串

问题描述

B 君有两个好朋友，他们叫宁宁和冉冉。有一天，冉冉遇到了一个有趣的题目：输入 $b, d, n$，求

$$
\bigg [ \Big ( \frac{b+ \sqrt{d}}{2} \Big )^n \bigg ]\mod 7528443412579576937
$$

输入格式

一行三个整数b,d,n。

输出格式

一行一个数表示模7528443412579576937 之后的结果。

样例输入 1

1 5 9

样例输出 1

76

样例输入 2

11 125 6715504

样例输出 2

1499928102740042526

提示

其中 $0<b^2 \leq d <(b+1)^2 \leq 10^{18}, \ n \leq 10^{18}$，并且 $b \mod 2=1, \ d \mod 4=1$

这个题直接上精度是吃不住的，需要观察出一个优美的式子，将原式写成
$$
\bigg[\bigg( \frac{b+\sqrt{d}}{2} \bigg)^n+\bigg(\frac{b-\sqrt{d}}{2}\bigg)^n\bigg]-\bigg(\frac{b-\sqrt{d}}{2}\bigg)^n
$$
这个式子我们发现最后一项由于题目所给的$b^2<=d<(b+1)^2$，那么只有当$b^2=d$时，它为0，其他情况下都是小数，只需要考虑$n$的奇偶就行了。因此我们主要看前面的部分。因此单独将他提出来
$$
\bigg(\frac{b+\sqrt{d}}{2}\bigg)^n+\bigg(\frac{b-\sqrt{d}}{2}\bigg)^n=\frac{1}{2^n}\bigg((b+\sqrt{d})^n+(b-\sqrt{d})^n\bigg)
$$
考虑括号内的二项式展开，当$\sqrt{d}$的次数为奇数时，这些项恰好两两抵消全部没了，因此剩下的项全都是$\sqrt{d}$的次数为偶数的项，我们猜测它一定是一个整数，考虑用数学归纳法证明，令$\alpha=\frac{b+\sqrt{d}}{2},\beta=\frac{b-\sqrt{d}}{2}$

当$n=0,1,2$时显然成立。

假设$n=k$时$\alpha^k+\beta^k$是整数，考虑
$$
(\alpha^k+\beta^k)(\alpha+\beta)=\alpha^{k+1}+\beta^{k+1}+\alpha\beta^k+\alpha^k\beta=\alpha^{k+1}+\beta^{k+1}+\frac{b-d^2}{4}\bigg(\alpha^{k-1}+\beta^{k-1}\bigg)
$$
由于$\alpha^k+\beta^k$与$\alpha+\beta$，$\alpha^{k-1}+\beta^{k-1}$都是整数，因此要证明$\alpha^{k+1}+\beta^{k+1}$是整数，只需要$\frac{b-d^2}{4}$是整数。

而考虑到题给条件，$b\ mod\ 2=1,d\ mod\ 4=1$，容易得到$b^2\ mod\ 4=1$，因此$\frac{b-d^2}{4}$是整数，故命题得证。

那么我们就可以先算出$\alpha^n+\beta^n$，最后再乘上$\frac{1}{2^n}$即可。

考虑用递推计算，实际上我们只需要算出$(b+\sqrt{d})^n$的整数部分系数再乘2即可

这个矩阵比较好推，由$[b,1]$开始，假设当前系数是$[x,y\sqrt{d}]$，那么再乘上一个$b+\sqrt{d}$后的系数就是$[xb+yd,by\sqrt{d}+x\sqrt{d}]$，因此转移矩阵出来了。

最后在考虑一开始提到的后面的一部分小数造成的影响即可，注意特判$n=0$的情况。

代码：

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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
#define ull unsigned long long
using namespace std;
const ull mod=7528443412579576937LL;
ull b,d,n;
ll ans;
ull A[3][3],Ans[3][3];
void add(ull &a,ull b){a+=b;a-=a>=mod?mod:0;}
ull QC(ull a,ull b)
{
	ull o=0;
	while(b)
	{
		if(b&1)add(o,a);
		b>>=1;add(a,a);
	}
	return o;
}
ull QM(ull a,ull b)
{
	ull o=1;
	while(b)
	{
		if(b&1)o=QC(o,a);
		b>>=1;a=QC(a,a);
	}
	return o;
}
void C(ull x[3][3],ull y[3][3])
{
	ull z[3][3],i,j,k;
	memset(z,0,sizeof(z));
	for(i=1;i<3;i++)
	for(j=1;j<3;j++)
	for(k=1;k<3;k++)add(z[i][j],QC(x[i][k],y[k][j]));
	memcpy(x,z,sizeof(z));
}
ull MQM(ull t)
{
	while(t)
	{
		if(t&1)C(Ans,A);
		t>>=1;C(A,A);
	}
	return Ans[1][1];
}
int main()
{
	ull x,y;
	scanf("%lld%lld%lld",&b,&d,&n);
	if(n==0)return puts("1"),0;
	A[1][1]=A[2][2]=b;A[1][2]=1;A[2][1]=d;
	Ans[1][1]=b;Ans[1][2]=1;
	x=MQM(n-1);x=QC(x,2);y=QM(mod+1>>1,n);
	ans=QC(x,y);
	if(b*b!=d)ans+=(n&1)?0:-1;
	printf("%lld",ans);
}