题目
Description
Read the program below carefully then answer the question.
#pragma comment(linker, “/STACK:1024000000,1024000000”)
#include
#include
#include
#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=(ans2+1)%m;
else ans=ans2%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.
Simple input
1 10
3 100
Simple output
1
5
题目分析
看到这个题的第一反应就是矩阵快速幂，事实证明也没有错，但是中间一度推出来了通项公式以为世界就是我的了，结果一直在WA，赛后知道通项公式没错但需要考虑特殊情况。
矩阵快速幂，首先右乘个奇数矩阵偶数矩阵的积(n/2)次，如果为奇数就在右乘一个奇数矩阵。
AC代码
1584K/0MS1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include<iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include<vector>
const int N = 2;
/*=========================================
矩阵快速幂
复杂度：O(N^3logK) N为矩阵大小，K为幂
=========================================*/
const int maxn = 20;
const int maxm = 20;
long long mod, k;
struct Matrix {
long long n, m;
long long a[maxn][maxm];
void clear() {
n = m = 0;
memset(a, 0, sizeof(a));
}
Matrix operator * (const Matrix &b) const { //实现矩阵乘法
Matrix tmp;
tmp.n = n;
tmp.m = b.m;
for (int i = 0; i < n; i++)
for (int j = 0; j < b.m; j++) tmp.a[i][j] = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
if (!a[i][j]) continue;
for (int k = 0; k < b.m; k++)
tmp.a[i][k] += a[i][j] * b.a[j][k], tmp.a[i][k] %= mod;
}
return tmp;
}
void Copy(const Matrix &b) {
n = b.n, m = b.m;
for (int i = 0; i < n; i++)
for(int j = 0; j < m; j++) a[i][j] = b.a[i][j];
}
void unit(int sz) {
n = m = sz;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) a[i][j] = 0;
a[i][i] = 1;
}
}
};
Matrix J, O;
void init() {
J.clear(); //矩阵A是构造的矩阵
J.n = J.m = 2;
J.a[0][0]=4;
J.a[0][1]=2;
J.a[1][0]=0;
J.a[1][1]=1;
O.clear();
O.n = 2;
O.m = 2; //矩阵B是f(x)的前10个数
O.a[0][0]=2;
O.a[0][1]=1;
O.a[1][0]=0;
O.a[1][1]=1;
}
Matrix Matrix_pow(Matrix A, long long k, long long mod) { //矩阵快速幂
Matrix res;
res.clear();
res.n = res.m = A.n;
for (int i = 0; i < A.n; i++) res.a[i][i] = 1;
while(k) {
if (k & 1) res.Copy(A * res);
k >>= 1;
A.Copy(A * A);
}
return res;
}
int main()
{
long long n,m;
while(scanf("%lld%lld",&n,&m)!=EOF)
{
init();
mod = m;
Matrix D;
D=Matrix_pow(J,n/2,m);
if(n&1)
D=O*D;
printf("%d\n",D.a[0][1]);
}
}