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

WQHui 2018-02-05 原文

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

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<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
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);
}