Problem Description Read the program below carefully then answer the question.
pragma comment(linker, “/STACK:1024000000,1024000000”)include includeinclude include include include
const int MAX=100000*2; const int INF=1e9;
int main() { int n,m,ans,i; while(scanf(“%d%d”,&n,&m)!=EOF) { ans=0; for(i=1;i<=n;i++) { if(i&1)ans=(ans*2+1)%m; else ans=ans*2%m; } printf(“%d\n”,ans); } return 0; }
Input Multi test cases，each line will contain two integers n and m. Process to end of file. [Technical Specification] 1<=n, m <= 1000000000
Output For each case，，output an integer，represents the output of above program.
Sample Input
1 10 3 100
Sample Output
1 5
Source BestCoder Round #8
Recommend heyang | We have carefully selected several similar problems for you: 5189 5188 5186 5185 5184
n很大,线性方法不行 第一个奇数是1,产生的1经过了n-1次乘法,最终是2^(n-1) 第二个奇数是3,产生的1经过了n-3次乘法,最终是2^(n-3) ……
因此最后就是2^(n – 1) + 2 ^ (n -3 ) + ….. 可以分n奇偶考虑 奇数: 2^0 + 2 ^ 2 + …. + 2 ^ (n-1) -> 4^0 + 4^1 + …+ 4 ^(n-1)/2 偶数:2 * (4^0 + 4^1 + … + 4^(n -2) / 2)
->矩阵快速幂求出即可
/*************************************************************************> File Name: hdu4990.cpp> Author: ALex> Mail: zchao1995@gmail.com> Created Time: 2015年03月15日 星期日 20时32分47秒 ************************************************************************/;const double pi = acos(-1.0);const int inf = 0x3f3f3f3f;const double eps = 1e-15;LL;typedef pair <int, int> PLL;LL mod, n;class MARTIX{public:LL mat[5][5];MARTIX();MARTIX operator * (const MARTIX &b)const;MARTIX& operator = (const MARTIX &b);}A;MARTIX::MARTIX(){memset (mat, 0, sizeof(mat));}MARTIX MARTIX :: operator * (const MARTIX &b)const{MARTIX ret;for (int i = 0; i < 3; ++i){for (int j = 0; j < 3; ++j){for (int k = 0; k < 3; ++k){ret.mat[i][j] += this -> mat[i][k] * b.mat[k][j];ret.mat[i][j] %= mod;}}}return ret;}MARTIX& MARTIX :: operator = (const MARTIX &b){for (int i = 0; i < 3; ++i){for (int j = 0; j < 3; ++j){this -> mat[i][j] = b.mat[i][j];}}return *this;}MARTIX fastpow(MARTIX ret, LL n){MARTIX ans;for (int i = 0; i < 3; ++i){ans.mat[i][i] = 1;}while (n){if (n & 1){ans = ans * ret;}ret = ret * ret;n >>= 1;}return ans;}void Debug(MARTIX A){for (int i = 0; i < 3; ++i){for (int j = 0; j < 3; ++j){printf(“%lld “, A.mat[i][j]);}printf(“\n”);}}int main (){while (~scanf(“%lld%lld”, &n, &mod)){A.mat[0][0] = A.mat[0][2] = 4 % mod;A.mat[0][1] = A.mat[2][2] = 1 % mod;MARTIX F;F.mat[0][0] = 4 % mod;F.mat[0][1] = 1 % mod;F.mat[0][2] = 5 % mod;if (n == 0 || n == 1 || n == 2){printf(“%lld\n”, n % mod);continue;}if (n & 1){int cnt = ((n – 1) >> 1);MARTIX ans = fastpow(A, cnt – 1);ans = F * ans;printf(“%lld\n”, ans.mat[0][2]);}else{MARTIX ans = fastpow(A, ((n – 2) >> 1) – 1);ans = F * ans;printf(“%lld\n”, ans.mat[0][2] * 2 % mod);}}return 0;}
生活若剥去了理想、梦想、幻想，那生命便只是一堆空架子
