「JLOI2015」有意义的字符串

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

「JLOI2015」有意义的字符串

题目描述

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

输入格式

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

输出格式

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

数据范围与提示

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

UPD：下面关于$\Big( \frac{b+ \sqrt{d}}{2}\Big )^n + \Big( \frac{b- \sqrt{d}}{2}\Big )^n $是整数的证明稍有问题，但是由于其中关于杨辉三角的运用很不错所以还是保留吧。

考虑与$\Big( \frac{b+ \sqrt{d}}{2}\Big )^n $形式相似的式子 $\Big( \frac{b- \sqrt{d}}{2}\Big )^n $。先不考虑分母上的$2^n$，那么两式相加之后结果一定是整数，因为$\sqrt d$次数为偶数的项自然是整数，而次数为奇数的项，前后正负相抵为0。

因此，$(b+\sqrt d)^n$和$(b-\sqrt d)^n$相加之后整数部分的值就是两倍 $(b+\sqrt d)^n$或$(b-\sqrt d)^n$整数部分的值。这个可以利用矩阵乘法加速计算。

///以下是有问题的证明

那么$\Big( \frac{b+ \sqrt{d}}{2}\Big )^n + \Big( \frac{b- \sqrt{d}}{2}\Big )^n $是否也是整数呢？由刚才的分析，分子部分是$2\sum_{i=0,i\ is \ even}^n\Big( ^n_i \Big) (\sqrt d)^i b^{n-i}$。现在考虑题目中对$b,d$的限制，在模2意义下考虑，则上述和式中组合数前的系数都是1。容易发现$\sum_{i=0,i\ is \ even}^n\Big( ^n_i \Big)$就是$2^{n-1}$，这个可以把杨辉三角画出来验证。此时再乘上和式前的系数2,恰好能将分子上的$2^n$约去。因此这个式子的结果是个整数，要得到它只需要用刚才矩阵乘法求出的值乘上2的逆元的n-1次方即可。(2的逆元就是把题目中的那个数加1之后除以2)

///以下是正确的证明：

先注意没有这样的事，这是上面证明的问题所在：

比如$a=b=5$就不满足上面的关系。但是有特例：

将$a$设为$2k+1$的形式后不难证明。

下面考虑使用数学归纳法证明$\Big( \frac{b+ \sqrt{d}}{2}\Big )^n + \Big( \frac{b- \sqrt{d}}{2}\Big )^n (n\in \mathbb N^*,b \mod 2=1, \ d \mod 4=1)$是整数。

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

假设结论对$1$~$n(n>2)$都成立，下面证明它对$n+1$也成立：

设$\alpha=\frac{b+ \sqrt{d}}{2}$,$\beta=\frac{b- \sqrt{d}}{2}$。由归纳假设得$(\alpha^n+\beta^n)(\alpha+\beta)$是整数。展开整理得$(\alpha^n+\beta^n)(\alpha+\beta)=\alpha^{n+1}+\beta^{n+1}+\alpha\beta(\alpha^{n-1}+\beta^{n-1})$。

由于$\alpha\beta=\frac{b^2-d}{4}$,由条件$b \mod 2=1, \ d \mod 4=1$得$\alpha\beta$是整数。由归纳假设得$\alpha^{n-1}+\beta^{n-1}$也是整数，所以$\alpha^{n+1}+\beta^{n+1}$是整数。

综上，$\Big( \frac{b+ \sqrt{d}}{2}\Big )^n + \Big( \frac{b- \sqrt{d}}{2}\Big )^n (n\in \mathbb N^*,b \mod 2=1, \ d \mod 4=1)$是整数。

之前都没有考虑原式，原式=$\Big[\Big( \frac{b+ \sqrt{d}}{2}\Big )^n + \Big( \frac{b- \sqrt{d}}{2}\Big )^n \Big]- \Big( \frac{b- \sqrt{d}}{2}\Big )^n$。由于$0<b^2 \leq d <(b+1)^2$,得到$b\leq \sqrt d< b+1$，所以$ \frac{b- \sqrt{d}}{2} \in (-1,0]$。仅当$n$为偶数且$b^2 \ne d$时，才需要把之前算得的结果减去1.

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
#include<stdio.h>
#include<cstring>
#include<iostream>
#include<cmath>
#define ull unsigned long long
using namespace std;
const ull mod=7528443412579576937ull,inv=3764221706289788469ull;

void add(ull &x,ull y){
	x+=y;
	x-=x<mod?0:mod;
}

ull B,D,N,Ans[10][10],f[10][10],ret;

ull ksc(ull a,ull b){
	ull ans=0;a%=mod;
	while(b){
		if(b&1)add(ans,a);
		b>>=1;add(a,a);
	}
	return ans;
}

ull ksm(ull a,ull b){
	ull ans=1;
	while(b){
		if(b&1)ans=ksc(ans,a);
		b>>=1;a=ksc(a,a);
	}
	return ans;
}

void mul(ull a[10][10],ull b[10][10]){
	ull c[10][10]={0};int i,j,k;
	for(k=1;k<=2;k++)
	for(i=1;i<=2;i++)
	for(j=1;j<=2;j++)
	add(c[i][j],ksc(a[i][k],b[k][j]));
	for(i=1;i<=2;i++)
	for(j=1;j<=2;j++)a[i][j]=c[i][j];
}

void KSM(ull b){
	f[1][1]=f[2][2]=B;f[1][2]=1;f[2][1]=D;
	Ans[1][1]=1;Ans[1][2]=0;
	while(b){
		if(b&1)mul(Ans,f);
		b>>=1;mul(f,f);
	}
}

int main(){
	cin>>B>>D>>N;
	if(N==0)return puts("1"),0;
	KSM(N);
	ret=ksc(Ans[1][1],ksm(inv,N-1));
	if((~N&1)&&B*B!=D)ret--;
	cout<<ret<<endl;
}