題解思路：

構造矩陣，矩陣乘法計算還是t;

需要找循環節;?? (注意因為是復合函數，不可以在里面取mod)

暴力跑只有可以找到g(222222224)%1e9==g(0)%1e9;

所以 g(g(n)%222222224)%1e9==g(g(n));

之后還可以跑出2個循環節

從內到外

240? 183120 222222224 1e9+7

#include<cstdio> #include<iostream> #include<cstring> #include<cmath> #include<algorithm> #include<queue> #include<set> #include<map> #include<stack>#define mem(a,b) memset(a,b,sizeof(a)) #define ll long long #define int long longconst int maxn=65000+10;using namespace std;int prime[maxn],is_prime[maxn];struct Matrix {int nmap[3][3]; };Matrix initA={0,0,0,0,1,0,0,0,1, };Matrix T= {0,0,0,0,0,0,0,0,0, };void is_p(){for(int i=2;i<=maxn;i++){if(!is_prime[i])for(int j=i+i;j<maxn;j+=i){is_prime[j]=1;}} }ll pow(ll a,ll b,ll mod) {ll sum=1;while(b){if(b&1) sum=(sum*a)%mod;a=(a*a)%mod;b>>=1;}return sum%mod; }void put(Matrix x) {for(int i=1;i<=2;i++){for(int j=1;j<=2;j++){cout<<x.nmap[i][j]<<" ";}cout<<endl;}cout<<endl; }Matrix Matrix_mul(Matrix a,Matrix b,int mod) {Matrix A=T;for(int k=1;k<=2;k++){for(int i=1;i<=2;i++){if(a.nmap[i][k])for(int j=1;j<=2;j++){A.nmap[i][j]+=(a.nmap[i][k]*b.nmap[k][j])%mod;A.nmap[i][j]%=mod;}}}return A; }Matrix Matrix_smul(Matrix a,int b,int mod) {Matrix A=initA;if(b==-1) return a;while(b){if(b&1) A=Matrix_mul(A,a,mod);a=Matrix_mul(a,a,mod);b>>=1;}return A; }#undef int int main(){ #define int long longMatrix C={0,0,0,0,3,1,0,1,0,};Matrix D={0,0,0,0,0,0,0,1,0,};int n=1,mod=1e9+7;while(~scanf("%lld",&n)){n%=240;mod=183120;Matrix B=Matrix_smul(C,n,mod);B=Matrix_mul(B,D,mod);// put(B)mod=222222224;B=Matrix_smul(C,B.nmap[1][1],mod);B=Matrix_mul(B,D,mod);// put(B);mod=1e9+7;B=Matrix_smul(C,B.nmap[1][1],mod);B=Matrix_mul(B,D,mod);// put(B);printf("%lld\n",B.nmap[1][1]);}// } /* int a=1,b=0,c,mod=240,ok=0;//跑循環節的代碼...for(int i=1;;i++){c=(3*a+b)%mod;b=a%mod;a=c%mod;if(a==1&&b==0){cout<<i<<endl;ok++;if(ok>10) break;}} */return 0; }

?

轉載于:https://www.cnblogs.com/minun/p/10473763.html

總結

以上是生活随笔為你收集整理的HDU 4291 A Short problem 矩阵快速幂 循环节的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。