BZOJ_4002_[JLOI2015]有意义的字符串_矩阵乘法

2022-11-03 14:08:03

Description

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

Input

一行三个整数 b;d;n

Output

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

Sample Input

1 5 9

Sample Output

HINT

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

$通过通项式可以求出递推式，具体的，
有递推式Ax_n+Bx_{n-1}+Cx_{n-2}=0$

$用Ax^{2}+Bx+C=0解出x_1,x_2,那么通项为S_n=(k_1*x_1)^{n}+(k_2*x_2)^{n}$

$首先设S_n=(\frac{b+\sqrt{d}}{2})^{n}+(\frac{b-\sqrt{d}}{2})^{n}$

$x_1=\frac{b+\sqrt{d}}{2},x_2=\frac{b-\sqrt{d}}{2}$

$A=1,B=b,C=\frac{b^{2}-d}{4}$

$之后就可以用矩阵乘法求S_n了，并且我们发现(\frac{b-\sqrt{d}}{2})^{n}的取值为[-1,1]$

$它对答案有贡献当且仅当n为偶数，b\not=\sqrt{d}$

代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <math.h>

using namespace std;

typedef unsigned long long ll;

typedef double du;

ll mod=7528443412579576937ll,b,d,n;

ll qc(ll x,ll y) {

    ll re=0;

    while(y>=1) {

        if(y&1ll) re=(re+x)%mod;

        x=(x+x)%mod;

        y>>=1ll;

    }

    return re;

}

struct Mat {

    ll v[2][2];

    Mat(){memset(v,0,sizeof(v));}

    Mat operator*(const Mat &x)const {

        Mat re;int i,j,k;

        for(i=0;i<2;i++) {

            for(j=0;j<2;j++) {

                for(k=0;k<2;k++) {

                    re.v[i][j]=(re.v[i][j]+qc(v[i][k],x.v[k][j]))%mod;

                }

            }

        }

        return re;

    }

};

Mat qp(Mat x,ll y) {

    Mat I;

    I.v[0][0]=I.v[1][1]=1;

    while(y>=1) {

        if(y&1ll) I=I*x;

        x=x*x;

        y>>=1ll;

    }

    return I;

}

int main() {

    scanf("%llu%llu%llu",&b,&d,&n);

    Mat x;

    x.v[0][0]=0; x.v[0][1]=(d-b*b)/4; x.v[1][0]=1; x.v[1][1]=b;

    Mat T=qp(x,n);

    ll ans=(qc(2,T.v[0][0])+qc(b,T.v[1][0]))%mod;

    if(d!=b*b&&n%2==0) ans--;

    printf("%llu\n",ans);

}

码农公寓