4002: [JLOI2015]有意义的字符串

Time Limit: 10 Sec  Memory Limit: 128 MB

Description

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

 

 

Input

一行三个整数 b;d;n

 

Output

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

 

Sample Input

1 5 9

Sample Output

76

HINT

 

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

 

Source

 

Tip：

　　高中有教过特征根方程；

　　当An=p*A(n-1)+q*A(n-2)时

　　x²=p*x+q的两个方程根x1,x2；

　　An=Ax1ⁿ+Bx2ⁿ；

　　此题x1=（b+d^0.5）/2，x2=（b-d^0.5）/2；

　　反解得p=b，q=（d-b*b）/4； 根据题意 q 算出来是一个整数。

　　An=（（b+d^0.5）/2）ⁿ+（（b-d^0.5）/2）ⁿ

　　（（b+d^0.5）/2）ⁿ=An-（（b-d^0.5）/2）ⁿ

　　-1 <= （（b-d^0.5）/2）ⁿ <= 1

　　当n为偶数且b！=d*d时-1，其余情况无影响；

　　用矩阵乘法求An即可；

　　注意unsigned long long，不过某些大佬好像没用，我也不清楚怎么做的%%%；

 

Code:

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const unsigned long long MOD=7528443412579576937;unsigned long long b,d,n,a[3][3],bb[3][3],ans[3][3],f,res;unsigned long long mul(unsigned long long aa,unsigned long long bb){    unsigned long long g=0; aa%=MOD;    for(unsigned long long i=bb;i;i>>=1,aa=aa*2%MOD)        if(i%2==1) g=(g+aa)%MOD;    return g;}void ch(){    for(int i=1;i<=2;i++)        for(int j=1;j<=2;j++){            bb[i][j]=0;            for(int k=1;k<=2;k++)                bb[i][j]=(bb[i][j]+mul(a[i][k],ans[k][j])%MOD)%MOD;        }    for(int i=1;i<=2;i++)        for(int j=1;j<=2;j++)            ans[i][j]=bb[i][j];}void cc(){    for(int i=1;i<=2;i++)        for(int j=1;j<=2;j++){            bb[i][j]=0;            for(int k=1;k<=2;k++)                bb[i][j]=(bb[i][j]+mul(a[i][k],a[k][j])%MOD)%MOD;        }    for(int i=1;i<=2;i++)        for(int j=1;j<=2;j++)            a[i][j]=bb[i][j];}int main(){    scanf("%lld%lld%lld",&b,&d,&n);    a[1][2]=1;    a[2][1]=(d-b*b)/4;    a[2][2]=b;    if(n%2==0 && b*b!=d) f=-1;    if(n==0){        printf("1");        return 0;    }    ans[1][1]=ans[2][2]=1;    while(n>0){        if(n%2==1) ch();        cc();        n=n/2;    }    res=(2*ans[1][1]%MOD+mul(ans[1][2],b))%MOD;    printf("%lld",(res+f+MOD)%MOD);}