正題

---

題目大意

有遞推式$$f_i=\prod _{j=1}^k{f}_{i?j}^{b_j}$$

給出$f_{1～k}$和$b_{1～k}$

求$f_n$

---

解題思路

首先這題的指數(shù)如此之大所以不能直接存，而指數(shù)又不能直接模所以我們要用歐拉定理
$$(b,p)=1$$
$$?a^b\equiv a^{b\%\phi (p)}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{p})$$
因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$p$為質(zhì)數(shù)所以就是
$$?a^b\equiv a^{b\%(p?1)}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{p})$$

然后對于答案肯定能表示成$$\prod _{j=1}^k{f}_k^{c_j}$$

那么對于$c$我們就可以用矩陣乘法求了

然后我們用矩陣乘法，用矩陣$G^n$中$(0,i)$表示$f_n$的$c_i$。

然后用矩陣乘法快速冪直接計(jì)算出$G^n$即可。

時(shí)間復(fù)雜度$:O(k^3\log n+k\log p)$

---

$code$

#pragma GCC optimize(2) #include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const int K=201,p=998244353,phi=998244352; int n,k,answer,num[K],b[K]; struct matrix{ll a[K][K];bool flag[K][K]; }f,ans,c; matrix operator*(const matrix &a,const matrix &b) {memset(c.a,0,sizeof(c.a));for(register int i=0;i<k;i++)for(register int j=0;j<k;j++)for(register int K=0;K<k;K++)c.a[i][j]=(c.a[i][j]+a.a[i][K]*b.a[K][j])%phi;return c; } int ksm(int x,int b) {int ans=1;while(b){if(b&1) ans=(ll)ans*x%p;x=(ll)x*x%p;b>>=1;}return ans; } int main() {//freopen("seq.in","r",stdin);//freopen("seq.out","w",stdout);scanf("%d%d",&n,&k);for(int i=1;i<k;i++)f.a[i][i-1]=1;for(int i=0;i<k;i++){scanf("%d",&b[i]);f.a[0][i]=b[i];}for(int i=0;i<k;i++)scanf("%d",&num[i]);if(n<=k){printf("%d",num[n-1]);return 0;}ans=f;n=n-k-1;while(n){ if(n&1) ans=ans*f;f=f*f;n>>=1;}answer=1;for(int i=0;i<k;i++)answer=(ll)answer*ksm(num[k-i-1],ans.a[0][i])%p;printf("%d",answer); }

總結(jié)

以上是生活随笔為你收集整理的jzoj6275-[NOIP提高组模拟1]小L的数列【矩阵乘法,欧拉定理】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。