这道题我写了两种写法
一种利用逆元 a/b%mod=a*c%mod; (c是b的逆元）易得2的逆元就是5~~~04；
一种是矩阵快速幂 利用递推式得出结论
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int mod=1000000007; int read(){ int ans=0,f=1,c=getchar(); while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();} return ans*f; } int n; int qmod(long long a,int b){ long long ans=1; a%=mod; while(b){ if(b&1) ans=ans*a%mod; b>>=1; a=a*a%mod; } return ans; } int main() { n=read()+1; printf("%lld ",(qmod(3,n)-1)*(long long)500000004%mod); return 0; }
#include<cstdio> #include<cstring> #include<algorithm> #define LL long long using namespace std; const int mod=1000000007; int read(){ int ans=0,f=1,c=getchar(); while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();} return ans*f; } typedef LL mat[2][2]; int n; void quickmod(mat a,mat b){ mat c={0}; for(int i=0;i<2;i++) for(int k=0;k<2;k++) for(int j=0;j<2;j++) c[i][j]=(c[i][j]+a[i][k]*b[k][j])%mod; for(int i=0;i<2;i++) for(int j=0;j<2;j++) a[i][j]=c[i][j]; } void fastpow(int n){ mat a={1,0,0,1},b={3,1,0,1}; while(n){ if(n&1) quickmod(a,b); n>>=1; quickmod(b,b); } printf("%d ",(a[0][0]+a[0][1])%mod); } int main() { n=read(); fastpow(n); return 0; }