for(i=1;i<=n;i++){ if(i&1)ans=(ans*2+1)%m; else ans=ans*2%m;} 给定n，m。让你用O(log(n))以下时间算出ans。
打表，推出 ans[i] = 2^(i-1) + f[i-2]
故 i奇数：ans[i] = 2^(i-1) + 2^(i-3) ... + 1;
i偶数：ans[i] = 2^(i-1) + 2^(i-3) ... + 2;
故可以用等比数列求和公式。
公式涉及除法。我也没弄懂为啥不能用逆元，貌似说是啥逆元可能不存在。
所以a/b % m == a%(b*m) / b 直接搞了。
#include#include #include #include #include #include typedef long long LL;LL quick_pow(LL a, LL b, LL m){ LL ans = 1, base = a % m; while(b) { if (b & 1) ans = (ans * base) % m; base = (base * base) % m; b >>= 1; } return ans;}int main(){ LL n, m; while(~scanf("%lld%lld", &n, &m)) { LL a1 = (n % 2) ? 1 : 2; LL sum = a1 * (quick_pow(4, (n+1)/2, 3*m) - 1); LL ans = (sum % (3 * m)) / 3; printf("%lld\n", ans); }}
第一次学矩阵快速幂，再贴个矩阵快速幂的板子。
f[n] = f[n-1] + 2 * f[n-2] + 1，故可以构造矩阵
f[n-2] f[n-1] 1 0 2 0 f[n-1] f[n] 10 0 0 1 1 0 = 0 0 00 0 0 0 1 1 0 0 0
模板来源：https://blog.csdn.net/u012860063/article/details/39123605
#include#include #include #include #include #include typedef long long LL;struct Matrix{ LL m[5][5];} I, A, B, T;LL a,b,n, mod;int ssize = 3;Matrix Mul(Matrix a,Matrix b){ int i,j,k; Matrix c; for (i = 1; i <= ssize; i++) for(j = 1; j <= ssize; j++) { c.m[i][j]=0; for(k = 1; k <= ssize; k++) { c.m[i][j]+=(a.m[i][k]*b.m[k][j]); c.m[i][j]%=mod; } } return c;}Matrix quickpagow(int n){ Matrix m = A, b = I; while(n) { if(n & 1) b = Mul(b, m); n >>= 1; m = Mul(m, m); } return b;}int main(){ while(~scanf("%lld%lld",&n, &mod)) { memset(I.m,0,sizeof(I.m)); memset(A.m,0,sizeof(A.m)); memset(B.m,0,sizeof(B.m)); for(int i = 1; i <= ssize; i++) I.m[i][i] = 1; //I是单位矩阵 B.m[1][1] = 1, B.m[1][2] = 2, B.m[1][3] = 1; A.m[1][2] = 2; A.m[2][1] = A.m[2][2] = A.m[3][2] = A.m[3][3] = 1; if(n == 1) printf("%lld\n",1 % mod); else if(n == 2) printf("%lld\n",2 % mod); else { T = quickpagow(n-2); T = Mul(B, T); printf("%lld\n",T.m[1][2] % mod); } }}