正題

題目鏈接:https://www.luogu.org/problem/U86650?contestId=23574

---

題目大意

第一年有$n$只雞，每只大于等于兩歲的雞每年可以生一只，在$t$歲時不會生雞而會暴斃。

現在給出每只雞的年齡，求第$m$年雞的總數量。

---

解題思路

用$f_i$表示年齡為$i$的雞的數量，然后矩乘優化即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const int N=75; struct matrix{ll a[N][N]; }f,ans; ll n,t,m,XJQ,num; matrix operator*(const matrix &a,const matrix &b){matrix c;memset(c.a,0,sizeof(c.a));for(ll i=0;i<t;i++)for(ll j=0;j<t;j++)for(ll k=0;k<t;k++)(c.a[i][j]+=a.a[i][k]*b.a[k][j]%XJQ)%=XJQ;return c; } matrix power(matrix x,ll b){matrix ans=x;b--;while(b){if(b&1) ans=ans*x;x=x*x;b>>=1;}return ans; } int main() {scanf("%lld",&n);for(ll i=1;i<=n;i++){ll x;scanf("%lld",&x);ans.a[0][x]++;}scanf("%lld%lld%lld",&t,&m,&XJQ);for(ll i=1;i<t;i++)f.a[i-1][i]++,f.a[i][0]++;f.a[t-1][0]--;f=power(f,m-1);ans=ans*f;for(ll i=0;i<t;i++)num=(num+ans.a[0][i])%XJQ;printf("%lld",num); }

總結

以上是生活随笔為你收集整理的U86650-群鸡乱舞【矩阵乘法】的全部內容，希望文章能夠幫你解決所遇到的問題。

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