HDU 5667 Sequence

正文索引 [隐藏]

题目翻译
题解
代码

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5667

题目翻译

求原题公式对P求余结果

题解

我们对原题的公式对(a)取对数，发现他是一个和前两项有关的加减递推式，于是我们可以用举证快速幂计算，然后a Mod P =0 时，要注意答案就是0.

代码

#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;
LL P;
LL n,a,b,c;
const int Maxn=5;
LL time_x[Maxn+5][Maxn+5];
LL time_tmp[Maxn+5][Maxn+5];
LL ans[Maxn+5];
LL tmp[Maxn+5];
inline void timeAns(){
    memset(tmp,0,sizeof(tmp));
    for (int i=1;i<=3;i++)
        for (int j=1;j<=3;j++)
            tmp[i]=(tmp[i]+ans[j]*time_x[i][j])%P;
    memcpy(ans,tmp,sizeof(ans));
}
inline void timeX(){
    memset(time_tmp,0,sizeof(time_tmp));
    for (int i=1;i<=3;i++)
        for (int j=1;j<=3;j++)
            for (int k=1;k<=3;k++)
                time_tmp[i][j]=(time_tmp[i][j]+time_x[i][k]*time_x[k][j])%P;
    memcpy(time_x,time_tmp,sizeof(time_x));
}
inline LL powX(LL x,LL ti){
    LL ret=1;
    x%=P;
    while(ti){
        if (ti&1) ret=(ret*x)%P;
        ti/=2LL;
        x=(x*x)%P;
    }
    return ret;
}
inline void solve(){
    scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&c,&P);
    ans[1]=b;
    ans[2]=0;
    ans[3]=b;
    memset(time_x,0,sizeof(time_x));
    time_x[1][1]=time_x[2][3]=time_x[3][1]=time_x[3][2]=1LL;
    time_x[3][3]=c;
    if (a%P==0 && n!=1){
        printf("0\n");
        return ;
    }
    P--;
    LL Ans=1;
    if (n==1){
        Ans=0;
    }else{
        n-=2;
        while(n){
            if (n&1) timeAns();
            n/=2LL;
            timeX();
        }
        Ans=ans[3];
        //printf("%lld\n",Ans);
    }
    P++;
    printf("%lld\n",powX(a,Ans));
}
int main(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    int T=0;
    while(scanf("%d",&T)!=EOF)
        for (int i=1;i<=T;i++)
            solve();
    return 0;
}

#include<cstdio>

#include<cstring>

#define LL long long

using namespace std;

LL P;

LL n,a,b,c;

const int Maxn=5;

LL time_x[Maxn+5][Maxn+5];

LL time_tmp[Maxn+5][Maxn+5];

LL ans[Maxn+5];

LL tmp[Maxn+5];

inline void timeAns(){

memset(tmp,0,sizeof(tmp));

for (int i=1;i<=3;i++)

for (int j=1;j<=3;j++)

tmp[i]=(tmp[i]+ans[j]*time_x[i][j])%P;

memcpy(ans,tmp,sizeof(ans));

}

inline void timeX(){

memset(time_tmp,0,sizeof(time_tmp));

for (int i=1;i<=3;i++)

for (int j=1;j<=3;j++)

for (int k=1;k<=3;k++)

time_tmp[i][j]=(time_tmp[i][j]+time_x[i][k]*time_x[k][j])%P;

memcpy(time_x,time_tmp,sizeof(time_x));

}

inline LL powX(LL x,LL ti){

LL ret=1;

x%=P;

while(ti){

if (ti&1) ret=(ret*x)%P;

ti/=2LL;

x=(x*x)%P;

}

return ret;

}

inline void solve(){

scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&c,&P);

ans[1]=b;

ans[2]=0;

ans[3]=b;

memset(time_x,0,sizeof(time_x));

time_x[1][1]=time_x[2][3]=time_x[3][1]=time_x[3][2]=1LL;

time_x[3][3]=c;

if (a%P==0 && n!=1){

printf("0\n");

return ;

}

P--;

LL Ans=1;

if (n==1){

Ans=0;

}else{

n-=2;

while(n){

if (n&1) timeAns();

n/=2LL;

timeX();

}

Ans=ans[3];

//printf("%lld\n",Ans);

}

P++;

printf("%lld\n",powX(a,Ans));

}

int main(){

freopen("in.txt","r",stdin);

freopen("out.txt","w",stdout);

int T=0;

while(scanf("%d",&T)!=EOF)

for (int i=1;i<=T;i++)

solve();

return 0;

}

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

WNJXYKの博客

喂你脚下有坑