张家港百度网站制作,重庆工信部网站,郑州全面恢复正常,做建筑材料哪个网站好一点正题 题目大意
有递推式fi∏j1kfi−jbjf_{i}\prod_{j1}^kf_{i-j}^{b_j}fij1∏kfi−jbj
给出f1∼kf_{1\sim k}f1∼k和b1∼kb_{1\sim k}b1∼k
求fnf_nfn 解题思路
首先这题的指数如此之大所以不能直接存#xff0c;而指数又不能直接模所以我们要用欧拉定理 (b…正题 题目大意
有递推式fi∏j1kfi−jbjf_{i}\prod_{j1}^kf_{i-j}^{b_j}fij1∏kfi−jbj
给出f1∼kf_{1\sim k}f1∼k和b1∼kb_{1\sim k}b1∼k
求fnf_nfn 解题思路
首先这题的指数如此之大所以不能直接存而指数又不能直接模所以我们要用欧拉定理 (b,p)1(b,p)1(b,p)1 ⇒ab≡ab%φ(p)(modp)\Rightarrow a^b\equiv a^{b\% \varphi(p)}(\rm mod\ p)⇒ab≡ab%φ(p)(mod p) 因为ppp为质数所以就是 ⇒ab≡ab%(p−1)(modp)\Rightarrow a^b\equiv a^{b\% (p-1)}(\rm mod\ p)⇒ab≡ab%(p−1)(mod p)
然后对于答案肯定能表示成∏j1kfkcj\prod_{j1}^kf_k^{c_j}j1∏kfkcj
那么对于ccc我们就可以用矩阵乘法求了
然后我们用矩阵乘法用矩阵GnG^nGn中(0,i)(0,i)(0,i)表示fnf_nfn的cic_ici。
然后用矩阵乘法快速幂直接计算出GnG^nGn即可。
时间复杂度:O(k3lognklogp):O(k^3\log nk\log p):O(k3lognklogp) codecodecode
#pragma GCC optimize(2)
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const int K201,p998244353,phi998244352;
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 i0;ik;i)for(register int j0;jk;j)for(register int K0;Kk;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 ans1;while(b){if(b1) ans(ll)ans*x%p;x(ll)x*x%p;b1;}return ans;
}
int main()
{//freopen(seq.in,r,stdin);//freopen(seq.out,w,stdout);scanf(%d%d,n,k);for(int i1;ik;i)f.a[i][i-1]1;for(int i0;ik;i){scanf(%d,b[i]);f.a[0][i]b[i];}for(int i0;ik;i)scanf(%d,num[i]);if(nk){printf(%d,num[n-1]);return 0;}ansf;nn-k-1;while(n){ if(n1) ansans*f;ff*f;n1;}answer1;for(int i0;ik;i)answer(ll)answer*ksm(num[k-i-1],ans.a[0][i])%p;printf(%d,answer);
}
