So the first thing you need to know is a posture, and if you do a Fib sequence or something like that, you’re going to get a loop node whenever you do a mod. So just beat the clock and find a pattern.
MOD = 1000000007 Discovery loop section is 222222224.
MOD = 2222222227 Found loop section is 183120
And then the problem was solved.
Don’t ask me why there are loop sections, and I won’t prove it…
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — line — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
I think I can prove it. Try it.
Let’s say that f(n) = (f(n-1)+f(n-2))%MOD.
Then the value range of f(n) is [0, mod-1], the total number of mods, that is, the total number of mods ×MOD combinations, and once the recursive formula is determined, the arrangement of the number of mods is determined, so there must be a cycle section.
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <cmath> #include <stack> #include <map> #pragma comment(linker, "/STACK:1024000000") #define EPS (1e-8) #define LL long long #define ULL unsigned long long #define INF 0x3f3f3f3f using namespace std; const int MAXN = 5; struct MAT { int row,col; LL mat[MAXN][MAXN]; void Init(int R,int C,int val) { row = R,col = C; for(int i = 1; i <= row; ++i) for(int j = 1; j <= col; ++j) mat[i][j] = (i == j ? val : 0); } MAT Multi(MAT c,LL MOD) { MAT tmp; tmp.Init(this->row,c.col,0); int i,j,k; for(k = 1; k <= this->col; ++k) for(i = 1; i <= tmp.row; ++i) for(j = 1; j <= tmp.col; ++j) (tmp.mat[i][j] += (this->mat[i][k]*c.mat[k][j])%MOD)%=MOD; return tmp; } MAT Quick(LL n,LL MOD) { MAT res,tmp = *this; res.Init(row,col,1); while(n) { if(n&1) res = res.Multi(tmp,MOD); tmp = tmp.Multi(tmp,MOD); n >>= 1; } return res; } void Output() { cout<<" **************** "<<endl; int i,j; for(i = 1; i <= row; ++i) { for(j = 1; j <= col; ++j) printf("%3d ",mat[i][j]); puts(""); } cout<<" &&&&&&&&&&&&& "<<endl; }}; int main() { const int M0 = 183120; const int M1 = 222222224; const int M2 = 1000000007; LL n; MAT A,B,tmp; Anderson, nit (2, 0); A.mat[1][1] = 0; A.mat[1][2] = 1; A.mat[2][1] = 1; A.mat[2][2] = 3; B.I nit (2, 0); B.mat[1][1] = 0; B.mat[2][1] = 1; while(cin>>n) { n = A.Quick(n,M0).Multi(B,M0).mat[1][1]; n = A.Quick(n,M1).Multi(B,M1).mat[1][1]; n = A.Quick(n,M2).Multi(B,M2).mat[1][1]; cout<<n<<endl; } return 0; }Copy the code