C - Reading comprehension
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Appoint description:
System Crawler (2016-04-25)
System Crawler (2016-04-25)
Description
Read the program below carefully then answer the question.
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include<iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include<vector>
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include<iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include<vector>
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
[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
3 100
Sample Output
1
5
5
思路：
if(i & 1) f[i] = f[i-1] * 2 + 1;
else f[i] = f[i-1] * 2;
所以这里有2个矩阵，关键的是什么，矩阵不满足交换律，所以先求出矩阵a和b的乘结果，然后在求a×b的n/2次方，如果n为奇数，补乘矩阵a即可。
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<cstdio>
#include<time.h>
#include<cstring>
#include<iostream>
#include<algorithm>
#define INF 1000000001
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int MAXN = ;
struct Mat
{
ll a[][];
};
ll MOD;
Mat operator *(Mat a,Mat b)
{
Mat c;
memset(c.a,,sizeof(c.a));
for(int i = ; i < ; i++){
for(int j = ; j < ; j++){
for(int k = ; k < ;k++){
c.a[i][j] += (a.a[i][k] * b.a[k][j])%MOD;
}
}
}
return c;
}
Mat power(Mat b,ll n)
{
Mat c;
c.a[][] = c.a[][] = ;
c.a[][] = c.a[][] = ;
while(n){
if(n & ){
c = c * b;
}
b = b * b;
n >>= ;
}
return c;
}
ll mod_pow(ll x,ll n)
{
ll res = ;
while(n){
if(n & ) res = res * x % MOD;
x = x * x % MOD;
n >>= ;
}
return res;
}
ll mod_mul(ll a,ll b)
{
ll res = ;
while(b){
if(b & ){
res = (res + a) % MOD;
}
b >>= ;
a = (a + a) % MOD;
}
return res;
}
ll n;
int main()
{
while(~scanf("%lld%lld",&n,&MOD)){
if(n == ){
cout<<<<endl;
continue;
}
else if(n == ){
cout<<%MOD<<endl;
continue;
}
Mat a,b;
a.a[][] = ;
a.a[][] = ;
a.a[][] = ;
a.a[][] = ;
b.a[][] = ;
b.a[][] = ;
b.a[][] = ;
b.a[][] = ;
a = power(a,n/);
if(n % == ){
ll ans = a.a[][] % MOD;
printf("%lld\n",ans);
}
else {
b = b * a;
ll ans = b.a[][] % MOD;
printf("%lld\n",ans);
}
}
return ;
}