思路:
#include<bits/stdc++.h>
using namespace std
;typedef long long ll
;ll mod
=1e9+7;ll
fp(ll x
,ll y
){ll ret
=1;while(y
){if(y
&1)ret
=ret
*x
%mod
; x
=x
*x
%mod
;y
/=2;}return ret
;
}int N
=3;struct matrix
{ll t
[5][5];
}rela
;ll t
[5][5]={0,0,1,0,0,1,0,1,0,0,0,1,1,0,0,
};ll tc
[5][5]={1,1,0,0,0,1,0,1,0,0,1,0,0,0,0,2,0,0,1,0,2,0,0,1,1
};
matrix
mul(matrix x
,matrix y
){matrix ans
; for(int i
=0;i
<N
;i
++)for(int j
=0;j
<N
;j
++){ans
.t
[i
][j
]=0;for(int k
=0;k
<N
;k
++){ans
.t
[i
][j
]+=x
.t
[i
][k
]*y
.t
[k
][j
]%mod
;ans
.t
[i
][j
]%=mod
;} }return ans
;
}matrix
fpow(matrix x
,ll y
){matrix ret
;memset(ret
.t
,0,sizeof(ret
));for(int i
=0;i
<N
;i
++)ret
.t
[i
][i
]=1; while(y
){if(y
&1)ret
=mul(ret
,x
);x
=mul(x
,x
); y
>>=1;}return ret
;
}int main(){ios
::sync_with_stdio(false
);ll n
,c
,f
[3],C_mi
;cin
>>n
>>f
[0]>>f
[1]>>f
[2]>>c
;n
-=3; ll ans
=1;matrix a
; mod
--;memcpy(rela
.t
,t
,sizeof(t
));a
=fpow(rela
,n
);mod
++;for(int i
=0;i
<3;i
++)ans
=ans
*fp(f
[i
],a
.t
[i
][2])%mod
;if(n
==1)C_mi
=2;else if(n
==2)C_mi
=6;else if(n
==3)C_mi
=14;else {ll init
[5]={14,6,2,3,1};n
-=3,N
=5;mod
--;memcpy(rela
.t
,tc
,sizeof(tc
)); a
=fpow(rela
,n
);C_mi
=0;for(int i
=0;i
<5;i
++){C_mi
+=init
[i
]*a
.t
[i
][0]%mod
;C_mi
%=mod
; }mod
++; } ans
=ans
*fp(c
,C_mi
)%mod
; cout
<<ans
<<endl
;
}
總結
以上是生活随笔為你收集整理的E. Product Oriented Recurrence(codeforces R566 div2)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
