首页 > 代码库 > 【HDU4990】递推式
【HDU4990】递推式
题目大意：给定序列 1， 2， 5， 10， 21， 42， 85， 170， 341 …… 求第n项 模 m的结果
递推式 f[i] = f[i - 2] + 2 ^ (i - 1);
方法一： 构造矩阵, 求递推式
方法二: 直接推公式，递推式求和，得到 f[n] = [2 ^ (n + 1) - 1] / 3 奇数， f[n] = [2 ^ (n + 1) - 2] / 3 偶数； 其实还可以进一步化简， 注意到 2 ^ 2k % 3 = 1, 2 ^ (2k + 1) % 3 = 2，于是 f[n] = 2 ^ (n + 1) / 3 ；于是答案就是 2 ^ (n + 1) % 3m / 3 (巧妙)
源码（矩阵）：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #define mem0(a) memset(a, 0, sizeof(a)) 7 #define LL __int64 8 using namespace std; 9 struct Node{10 LL a[2][2];11 };12 Node multi(Node a, Node b, int m)13 {14 Node ans;15 mem0(ans.a);16 for(int i = 0; i < 2; i++) {17 for(int j = 0; j < 2; j++) {18 for(int k = 0; k < 2; k++) {19 ans.a[i][j] += (a.a[i][k] * b.a[k][j]) % m;20 }21 }22 }23 return ans;24 }25 Node calc(Node a, int b, int m)26 {27 if(b == 1) return a;28 Node tmp = calc(a, b >> 1, m);29 int t = b & 1;30 tmp = multi(tmp, tmp, m);31 if(t) tmp = multi(tmp, a, m);32 return tmp;33 }34 Node a0;35 int main()36 {37 //freopen("in.txt", "r", stdin);38 int n, m;39 a0.a[0][0] = a0.a[1][0] = 1;40 a0.a[0][1] = 0;41 a0.a[1][1] = 4;42 while(~scanf("%d%d", &n, &m)) {43 LL ans = 0;44 if(n == 1) {45 cout<< 1 % m<< endl;46 continue;47 }48 if(n == 2) {49 cout<< 2 % m<< endl;50 continue;51 }52 if(n & 1) {53 Node one = calc(a0, (n - 1) >> 1, m);54 ans = (one.a[0][0] + one.a[1][0] * 4) % m;55 }56 else {57 Node one = calc(a0, (n - 2) >> 1, m);58 ans = (one.a[0][0] * 2 + one.a[1][0] * 8) % m;59 }60 cout<< ans<< endl;61 }62 return 0;63 }
【HDU4990】递推式
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。