锐客网

  1. 首页 > it技术 > >

Reading comprehension

题解

【Reading comprehension】题意:Fi满足:if (i & 1)ans = (ans * 2 + 1) % m; else ans = ans * 2 % m; ,给出n,m，问Fn为多少。
当i为奇数时,Fi=4F(i-1)+1,当j为偶数时，Fj=4F(j-1)+2.我们可以得到这样一个关系：
Reading comprehension
文章图片

#include #include #include #includeusing namespace std; typedef long long ll; const int N = 2e5 + 10; int arr[N]; ll mod; struct matrix { ll rix[5][5]; }ans,test; ll quick_pow(ll a,ll b) { ll ans = 1; a %= mod; while (b) { if (b & 1) ans = (ans + a) % mod; a = (a + a) % mod; b >>= 1; } return ans; }matrix mul(int n,matrix rix1,matrix rix2) { matrix temp; memset(temp.rix, 0, sizeof(temp.rix)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { for (int k = 1; k <= n; k++) { temp.rix[i][j] = (temp.rix[i][j] + rix1.rix[i][k] * rix2.rix[k][j])%mod; } } } return temp; }void quick_rix(int n,int k) { memset(ans.rix, 0, sizeof(ans.rix)); for (int i = 1; i <= n; i++) ans.rix[i][i] = 1; while (k) { if (k & 1) ans = mul(n,ans,test); test = mul(n, test, test); k >>= 1; } //return ans; }int main() { ios::sync_with_stdio(false); matrix rax; int n; while (cin >> n >> mod) { memset(rax.rix, 0, sizeof(rax.rix)); memset(test.rix, 0, sizeof(test.rix)); rax.rix[1][1] = 1; rax.rix[2][1] = 2; rax.rix[1][2] = 1; rax.rix[2][2] = 2; test.rix[1][1] = 4; test.rix[2][1] = 1; test.rix[1][2] = 0; test.rix[2][2] = 1; if (n == 1) { cout << (rax.rix[1][1] + mod) % mod << endl; } else if (n == 2) { cout << (rax.rix[2][1] + mod) % mod << endl; } else { quick_rix(2, (n - 1) / 2); ans = mul(2, rax, ans); if (n & 1) { cout << (ans.rix[1][1] + mod) % mod << endl; } else { cout << (ans.rix[2][1] + mod) % mod << endl; } } } }

    推荐阅读


    上一篇：你好旧时光

    下一篇：从零开始学习ASP.NET|从零开始学习ASP.NET MVC 1.0 (一) 开天辟地入门篇