【数列求值 / B】

题目

一般做法

#include <bits/stdc++.h>
using namespace std;
const int mod = 10000; 
int f[20190325] = {1, 1, 1, 1};
int main()
{for(int i = 4; i <= 20190324; i++){f[i] = (f[i-1] + f[i-2] + f[i-3]) % mod;}cout << f[20190324];
}

快速幂+矩阵乘法

#include <bits/stdc++.h>
using namespace std;
const int mod = 10000; 
void mul(int C[], int A[], int B[][3])
{int temp[3] = {0};for(int i = 0; i < 1; i++){for(int j = 0; j < 3; j++){for(int k = 0; k < 3; k++){temp[j] = (temp[j] + A[k] * B[k][j]) % mod;}}}memcpy(C, temp, sizeof temp);
}
void mul(int C[][3], int A[][3], int B[][3])
{int temp[3][3] = {0};for(int i = 0; i < 3; i++){for(int j = 0; j < 3; j++){for(int k = 0; k < 3; k++){temp[i][j] = (temp[i][j] + A[i][k] * B[k][j]) % mod;}}}memcpy(C, temp, sizeof temp);
}
void qmi(int A[], int B[][3], int i)
{while(i){if(i&1) mul(A,A,B);mul(B,B,B);i >>= 1;}
}
int main()
{int A[3] = {1, 1, 1};int B[3][3] = {{0,0,1},{1,0,1},{0,1,1}};qmi(A,B,20190321);cout << A[2] % mod;
}

#include <bits/stdc++.h>
using namespace std;
const int mod = 10000; 
void mul(int C[][3], int A[][3], int B[][3])
{int temp[3][3] = {0};for(int i = 0; i < 3; i++){for(int j = 0; j < 3; j++){for(int k = 0; k < 3; k++){temp[i][j] = (temp[i][j] + A[i][k] * B[k][j]) % mod;}}}memcpy(C, temp, sizeof temp);
}
void qmi(int A[][3], int B[][3], int i)
{while(i){if(i&1) mul(A,A,B);mul(B,B,B);i >>= 1;}
}
int main()
{int A[3][3] = {{1, 1, 1}};int B[3][3] = {{0,0,1},{1,0,1},{0,1,1}};qmi(A,B,20190321);cout << A[0][2] % mod;
}