#10193 “The k-th number of Yibentong 6.1 Example 1” sequence
3A When taking the modulus, remember to take the global modulus… if you can take it, you must take it
#10195 “One Book Through 6.1 Exercise 2 “Rounding Game
2A, it is the same as the above question. For the problem of turning in a circle, we must take the modulus!
#10196 “Yibentong 6.1 Exercise 3” Jailbreak
1AQuick Power Topic I’m here to teach you how to take the modulus……………… Note that when subtracting, you must add the modulus and then take the modulus.
- The n, m, p enumeration order of the moment multiplication Whatever
#10221 “Yibentong 6.5 Example 3” Fibonacci the first n item and
If you want to maintain the sum of each item in the linear recursion, add one more dimension and record the prefix sum.
In terms of state definition: how to push and how to be comfortable.
Note that there is no commutative law in Matrices, so be careful when writing persimmons!
but,we have Black Technology:
S(n)=Fib(n+ 2)-1
int n,mod;struct Matrix{ int m[4][4]; Matrix(){mem(m,0);} friend Matrix operator *(Matrix a,Matrix b){ Matrix c; rep(i,1,3) rep(k,1,3) rep(j,1,3) cm[i][j]=(cm[i ][j]+am[i][k]*bm[k][j])%mod; return c;} friend Matrix operator ^(Matrix a,int k){ Matrix res; rep(i,1,3 )res.m[i][i]=1; for(;k;k>>=1){ if(k&1)res=res*a; a=a*a;} return res; }};#undef intint main(){#define int long long #ifdef WIN32 freopen("a.txt","r",stdin); #endif rd(n),rd(mod); Matrix base,ans; ans.m[1 ][1]=1,ans.m[1][2]=1,ans.m[1][3]=1;//sum[1] f[2] f[1] base.m[1 ][1]=1,base.m[1][2]=0,base.m[1][3]=0; base.m[2][1]=1,base.m[2][ 2]=1,base.m[2][3]=1; base.m[3][1]=0,base.m[3][2]=1,base.m[3][3] =0; base=base^(n-1); ans=ans*base; printf( "%lld\n",ans.m[1][1]%mod); return 0;}
P4838 P Ge crack password
First of all, you have to see that this is a linear recursion, which is transferred from how many A’s in the previous state.
Range: 1e9 linear recursion, then, on , Momentum!
Set: \(f[i][j]\) means transfer to i-digit string, i-th Fill in the legal number of sets of j A.
Transfer:
f[i][0]=f[i-1][0]+f[i-1][1] +f[i-1][2];//When the i-th place is filled with B, it can be transferred from the previous place with B, A, AA.
f[i][1]=f[i- 1][0]//When the i-th place is filled with A, it can be transferred from the previous place with B-filled
f[i][2]=f[i-1][1]//The i-th place When filling in AA, it can be transferred from the previous one and filling in A
/* Transfer matrix:
1 1 0
1 0 1
1 0 0
*/
Final state:f[n][0]+f[n][1]+f[n][2]
Initialization:
f[1][0]=1,f[1][1]=1,f[1][2]=0;
BTW: To find the legal number of strings of length n, then only need to transfer n-1 times (because the legal string of length 1 has been preprocessed Number)
Note: I did not use the “0” subscript in the base matrix, which I thought was troublesome. So all subscripts are added with 1
int n;const int mod=19260817;struct Matrix {int m[4][4]; Matrix(){mem( m,0);} friend Matrix operator *(Matrix a,Matrix b){ Matrix c; rep(i,1,3) rep(k,1,3) rep(j,1,3) cm[i][ j]=(cm[i][j]+am[i][k]*bm[k][j])%mod; return c;} friend Matrix operator ^(Matrix a,int k){ Matrix res; rep(i,1,3)res.m[i][i]=1; for(;k;k>>=1){ if(k&1)res=res*a; a=a*a;} return res; }};#undef intint main(){#define int long long #ifdef WIN32 freopen("a.txt","r",stdin); #endif int T;rd(T); while(T-- ){ rd(n); Matrix ans,base; ans.m[1][1]=1,ans.m[1][2]=1,ans.m[1][3]; base.m[ 1][1]=1,base.m[1][2]=1,base.m[1][3]=0; base.m[2][1]=1,base.m[2] [2]=0,base.m[2][3]=1; base.m[3][1]=1,base.m[3][2]=0,base.m[3][3 ]=0; base=base^(n-1); ans=ans*base; printf("%lld\n",(ans.m[1][1]+ans.m[ 1][2]+ans.m[1][3])%mod);} return 0;}