题意：给一个数列a[i]=2a[i-1](如果i是偶数) a[i]=2a[i-1]+1(如果i是奇数)；求a[n]%m (1<=n, m <= 1000000000)
思路：明显用矩阵快速幂，，可以推出通项：a[n]=2*a[n-2]+a[n-1]+1
当然并不需要动脑…直接当成偶数处理就好，是奇数的话单独再递推一项就好。也就是a[i]=4a[i-2]+2
//4990 0MS 1620K 1196 B C++ #include<cstdio>#include<iostream>#include<cstring>#include<algorithm>using namespace std;typedef long long ll;ll n,mod;struct mat{ll a[3][3];mat(){memset(a,0,sizeof(a));}};mat I;mat mul(mat m1,mat m2){mat ans;for(int i=1;i<=2;i++)for(int j=1;j<=2;j++)for(int k=1;k<=2;k++)ans.a[i][k]=(ans.a[i][k]+m1.a[i][j]*m2.a[j][k])%mod;return ans;}mat quickmul(mat m,int k){mat ans;ans.a[1][1]=ans.a[2][2]=1;while(k){if(k&1) ans=mul(ans,m);m=mul(m,m);k>>=1;}return ans;}int main(){while(~scanf("%I64d%I64d",&n,&mod)){I.a[1][1]=4,I.a[1][2]=2,I.a[2][1]=0,I.a[2][2]=1;ll k=n/2;mat t=quickmul(I,k);ll ans=t.a[1][2]%mod;if(n%2) ans=(ans*2+1)%mod;printf("%I64d\n",ans);}return 0;}
有理想在的地方，地狱就是天堂
