洛谷 P3263 [JLOI2015]有意义的字符串
admin
2024-04-03 05:30:45
0

PS:如果读过题了可以跳过题目描述直接到题解部分
提交链接:洛谷 P3263 [JLOI2015]有意义的字符串

题目

题目描述

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

⌊(b+d2)n⌋modp\lfloor ( \frac{b+\sqrt{d}}{2} ) ^n \rfloor \mathrm{mod} \ p⌊(2b+d​​)n⌋mod p

其中p=7528443412579576937p=7528443412579576937p=7528443412579576937

输入格式

一行三个整数 b;d;n

输出格式

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

样例 #1

样例输入 #1

1 5 9

样例输出 #1

76

提示

其中 0

题解

看到 (b+d2)n( \frac{b+\sqrt{d}}{2} ) ^n(2b+d​​)n 的时候,数学比较好的人应该就会反应出一个平方差公式,所以就会想到 (b−d2)n( \frac{b-\sqrt{d}}{2} ) ^n(2b−d​​)n,那么我们会发现,这两个是方程x2−bx+b2−d4=0x^2-bx+\frac{b^2-d}{4}=0x2−bx+4b2−d​=0的两根。
移项可得:x2=bx+b2−d4x^2=bx+\frac{b^2-d}{4}x2=bx+4b2−d​
再同时乘以xn−2x^{n-2}xn−2可得:xn=bxn−1+b2−d4xn−2x^n=bx^{n-1}+\frac{b^2-d}{4}x^{n-2}xn=bxn−1+4b2−d​xn−2
令fi=(b+d2)i+(b−d2)if_i=( \frac{b+\sqrt{d}}{2} ) ^i+( \frac{b-\sqrt{d}}{2} ) ^ifi​=(2b+d​​)i+(2b−d​​)i,则fif_ifi​为整数,且fi=bfi−1+b2−d4fi−2f_i=bf_{i-1}+\frac{b^2-d}{4}f_{i-2}fi​=bfi−1​+4b2−d​fi−2​,f0=2f_0=2f0​=2,f1=bf_1=bf1​=b,所以可以用矩阵乘法求出fnf_nfn​(因为会爆long long,所以推荐用__int128)

最后当b2≠db^2≠db2=d且nnn为偶数的时候,答案为fn−1f_n-1fn​−1,否则为fnf_nfn​。

注意不要把矩阵初始化的时候打错了,我调了一个多小时,最后发现是初始化的时候有两个写反了。

代码实现

100pts

//洛谷 P3263 [JLOI2015]有意义的字符串
#pragma GCC optimize(3)
#include
#include
using namespace std;
const __int128 p=7528443412579576937;
__int128 b,d,n;
__int128 z[2][2];
__int128 a[2][2];
__int128 s[2][2];void mi(__int128 n){while(n){if(n&1){for(int i=0;i<=1;++i){for(int j=0;j<=1;++j){s[i][j]=(z[i][0]*a[0][j]+z[i][1]*a[1][j])%p;}}for(int i=0;i<=1;++i){for(int j=0;j<=1;++j){a[i][j]=s[i][j];}}}for(int i=0;i<=1;++i){for(int j=0;j<=1;++j){s[i][j]=(z[i][0]*z[0][j]+z[i][1]*z[1][j])%p;}}for(int i=0;i<=1;++i){for(int j=0;j<=1;++j){z[i][j]=s[i][j];}}n>>=1;}
}void in(__int128 &x){int nt;x=0;while(!isdigit(nt=getchar()));x=nt^'0';while(isdigit(nt=getchar())){x=(x<<3)+(x<<1)+(nt^'0');}
}inline void wr(__int128 x)
{if(x<0) putchar('-'),x=-x;if(x>9) wr(x/10);putchar(x%10+'0');
}int main(){in(b),in(d),in(n);z[0][1]=1;z[1][0]=((d-b*b)/4)%p;z[1][1]=b;a[0][0]=1;a[1][1]=1;mi(n);if(b*b!=d&&n%2==0){wr((a[0][0]*2%p+b*a[0][1]-1)%p);}else{wr((a[0][0]*2%p+b*a[0][1])%p);}return 0;
}

相关内容

热门资讯

安卓系统所有手机通用,揭秘所有... 你有没有发现,现在市面上各种各样的手机,品牌琳琅满目,让人挑花了眼?不过,不管你用的是哪个品牌的手机...
安卓系统变ios系统好用吗,体... 你有没有想过,为什么有些人从安卓手机换到了苹果的iPhone,而且好像换了之后整个人都精神焕发呢?没...
华为安卓系统文件删除,轻松掌握... 你有没有遇到过这种情况?手机里的文件突然不见了,尤其是华为安卓系统里的那些重要文件,真是让人心头一紧...
安卓1.5系统软件,初代智能革... 你有没有想过,手机里的那些看似普通的系统,其实背后藏着无数的故事呢?今天,就让我带你走进安卓1.5系...
安卓 代替系统音效设置,打造个... 你有没有发现,手机里的那些系统音效有时候真的让人有点烦躁呢?比如那个每次接电话时“叮咚”一声,或者是...
安卓系统整体性,构建移动设备的... 你知道吗?在智能手机的世界里,安卓系统就像是个全能的魔术师,它不仅拥有丰富的魔法,还能让各种神奇的魔...
安卓系统能玩鬼泣么?,畅享动作... 你有没有想过,在安卓系统上玩《鬼泣》这款游戏会是怎样的体验呢?没错,就是那个让你热血沸腾、挑战极限的...
安卓系统手机编曲软件,音乐创作... 你有没有想过,用手机也能轻松编曲?没错,就是那个你每天不离手的安卓系统手机!现在,我就要给你揭秘几款...
车载导航显示安卓系统,车载导航... 你有没有发现,现在的车载导航系统越来越智能了?尤其是那些搭载了安卓系统的车载导航,简直就像是个贴心的...
安卓系统启动黑屏,安卓系统启动... 手机屏幕突然黑了,这可怎么办?别急,今天就来和你聊聊安卓系统启动黑屏这个让人头疼的问题。你知道吗,这...
怎么解除订阅安卓系统,安卓系统... 你是不是也和我一样,手机里订阅了好多服务,结果现在想解除订阅,却一头雾水?别急,今天就来手把手教你如...
安卓系统停用怎么开启,轻松恢复... 亲爱的手机控们,你是否曾经遇到过安卓系统突然停用的情况,让你手忙脚乱,不知所措?别担心,今天就来教你...
安卓系统电池健康度,电池健康度... 你有没有发现,你的安卓手机最近是不是有点儿不给力了?电池续航能力大不如前,充电速度也慢了不少?别急,...
安卓系统按键怎么截图,安卓系统... 你是不是也和我一样,有时候想截个图分享给朋友,却发现安卓手机的截图功能有点神秘呢?别急,今天就来手把...
购票系统安卓源代码,架构设计与... 你有没有想过,那些我们每天离不开的购票系统,它们背后的秘密是什么呢?今天,就让我带你一探究竟,揭开购...
安卓手机系统后台测试,深度解析... 你有没有发现,你的安卓手机后台总是悄悄地忙碌着?别小看了这些后台程序,它们可是手机系统稳定运行的关键...
安卓系统重启的图标,解锁设备新... 手机突然重启,是不是心里有点慌?别急,今天就来和你聊聊安卓系统重启的图标,让你一眼就能认出它,再也不...
车载智慧屏安卓系统,智能出行新... 你有没有发现,现在的车载智慧屏越来越智能了?尤其是那些搭载了安卓系统的,简直就像是个移动的小电脑,不...
安卓系统连上网权限,解锁设备无... 你有没有发现,你的安卓手机里有些应用总是偷偷连上网?别小看这个小小的网络权限,它可是能影响你隐私、消...
安卓谷歌操作系统,探索安卓谷歌... 你知道吗?在智能手机的世界里,有一个操作系统可是无人不知、无人不晓,那就是安卓谷歌操作系统。它就像一...