BZOJ 4002 有意义的字符串

题目：

给定b,d,n，求⌊(2b+d​​)n⌋mod7528443412579576937。

其中，0<b2≤d≤(b+1)2≤1018,n≤1018，并且bmod2=1,dmod4=1

思路：

求这样一个东西的n次方然后向下取整，再取模，这很显然是不能够直接快速幂的。所以对下取整里面的东西进行考虑。将(2b+d​​)n二项式展开，会发现只有d​的奇数次项是小数，其余都是整数。因此可以通过加上(2b−d​​)n来消去d​的奇数次项。

所以我们将所求转化为⌊[(2b+d​​)n+(2b−d​​)n]−(2b−d​​)n⌋ 。

对于前半部分，这样的形式正好对应了二阶线性递推的通项的形式。

令x1​=2b+d​​,x2​=2b−d​​ ，则原式前半部分变成x1n​+x2n​

令f(n)=x1n​+x2n​，则该函数的二阶线性递推式为

f(n)−(x1​+x2​)f(n−1)+(x1​x2​)f(n−2)=0

化简得

f(n)=(x1​+x2​)f(n−1)−(x1​x2​)f(n−2)

f(n)=bf(n−1)+4d−b2​f(n−2)

对于后半部分，可以发现⌊d​⌋=b，所以0≤∣(b−