nbhkdz.com冰点文库

hdu4549


#include<cstdio> #include<cstring> #define?MO1?1000000007 #define?MO2?1000000006 #define?ll?long?long?int using?namespace?std; struct?nodej { ll?d[2][2]; }; nodej?operator*(nodej?

a,nodej?b) { nodej?ans; int?f1; int?f2; int?f3; memset(ans.d,0,sizeof(ans.d)); for(f1=0;f1<2;f1++) for(f2=0;f2<2;f2++) for(f3=0;f3<2;f3++) { ans.d[f1][f2]+=a.d[f1][f3]*b.d[f3][f2]; ans.d[f1][f2]%=MO2; } return?ans; } nodej?operator^(nodej?a,ll?b) { nodej?ans; for(ans.d[0][0]=ans.d[1][1]=1,ans.d[0][1]=ans.d[1][0]=0;b!=0;b>>=1) { if(b&1) ans=ans*a; a=a*a; } return?ans; } ll?kmi(ll?a,ll?b) { ll?ans; for(ans=1;b!=0;b>>=1) { if(b&1) ans=ans*a%MO1; a=a*a%MO1; } return?ans; } int?main() { nodej?l; ll?z1; ll?z2; ll?ci; while(scanf("%lld%lld%lld",&z1,&z2,&ci)!=EOF) { l.d[0][0]=l.d[0][1]=l.d[1][0]=1;

l.d[1][1]=0; l=l^ci; printf("%lld\n",kmi(z1,l.d[1][1])*kmi(z2,l.d[0][1])%MO1); } return?0; }