題目鏈接：點擊查看

題目大意：初始化：第一行依次為233,2333,23333....第一列依次為a0,a1,a2....(題目中會給出)，再給出遞推公式：，求矩陣中第n行m列的數字是多少

題目分析：因為給出的列數最高能到1e9，所以肯定不能暴力模擬打表，如果暴力打表連數組都開不起來，如果滾動數組模擬，會爆時間，因為這個題目給出了遞推式，所以可以向矩陣快速冪的角度出發，一開始給出的是第一列的數列，我們可以嘗試從第一列推到第二列，上個圖能更好的幫助理解：

如圖，在已知目前藍色一列的情況下，可以將每個圖中的藍色方塊加和，就可以得到紅色方塊的結果了，而最上面的藍色方塊我們可以再矩陣中多維護兩行信息來遞推2333，下面構造矩陣，以n=5為例子：

每個樣例給出n個常數，但是我們需要維護一個n+2的矩陣，其中多出來的兩行維護的是第一行的信息，看了上面的矩陣應該一目了然了，剩下的套板子就好了，不多贅述了

對了，需要注意的是最后在乘法運算加和的時候會爆int，記得轉換成longlong緩沖一下就好了（其實一般矩陣快速冪的題目過了樣例卻還是WA的話就要考慮爆int的問題了，遇到好多次了。。）

#include<iostream> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> using namespace std;typedef long long LL;const int N=15;const int M=10000007;int n,m;int f[N];struct Ma {int a[N][N]; };Ma operator *(Ma a,Ma b) {Ma temp;for(int i=0;i<n+2;i++)for(int j=0;j<n+2;j++){temp.a[i][j]=0;for(int k=0;k<n+2;k++)temp.a[i][j]=(temp.a[i][j]+((LL)a.a[i][k]*b.a[k][j])%M)%M;}return temp; }Ma Pw(Ma a,int b) {Ma ans;memset(ans.a,0,sizeof(ans.a));for(int i=0;i<n+2;i++)ans.a[i][i]=1;while(b){if(b&1)ans=ans*a;a=a*a;b>>=1;}return ans; }int main() {while(scanf("%d%d",&n,&m)!=EOF){Ma ans;int q;memset(ans.a,0,sizeof(ans.a));for(q=0;q<n;q++)scanf("%d",&f[q]);f[q++]=233;f[q++]=3;for(int i=0;i<n;i++){ans.a[i][n]=1;for(int j=0;j<n;j++)if(j<=i)ans.a[i][j]=1;}ans.a[n][n]=10;ans.a[n][n+1]=ans.a[n+1][n+1]=1;ans=Pw(ans,m);/* for(int i=0;i<q;i++){for(int j=0;j<q;j++)cout<<ans.a[i][j]<<' ';cout<<endl;}cout<<endl;for(int i=0;i<q;i++)cout<<f[i]<<' ';cout<<endl;*/int sum=0;for(int i=0;i<q;i++)sum=(sum+((LL)f[i]*ans.a[n-1][i])%M)%M;cout<<sum<<endl;}return 0; }

?

總結

以上是生活随笔為你收集整理的HDU - 5015 233 Matrix(矩阵快速幂)的全部內容，希望文章能夠幫你解決所遇到的問題。

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