題目鏈接：點擊查看

題目大意：規定寬度為4，給定長度為n，求用1*2和2*1的瓷磚，將其完全鋪滿能有多少種方法。

分析：自從學會了矩陣快速冪之后，看到1e18的數據量都會下意識的往遞推上面想，但是以前都是因為找不到規律而止步不前。今天看到了一個大佬的博客之后，學會了一個新的方法，這個方法學長上課也講了，如果按照正規做法的話應該用高斯消元法求遞推式，但是相應的，用暴力的手法也能硬湊出遞推關系式：https://www.cnblogs.com/yzm10/p/9313916.html

2020.7.18更新：

大半夜睡不著覺回顧以前的博客，發現這個題不就是個杜教BM嘛，爆搜找出前10項然后直接套上模板就過了

注意有一點，利用這個方法只能解決線性問題，非線性的規律是不能用這個方法處理的

第一步：通過暴搜找出前幾個數據：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e4+200;int n,ans;bool vis[N][N];void dfs(int s)//s代表已放置瓷磚面積 {if(s==4*n){ans++;return;}for(int i=0;i<4;i++)for(int j=0;j<n;j++){if(!vis[i][j]){if(i+1<4&&!vis[i+1][j]){vis[i+1][j]=vis[i][j]=true;dfs(s+2);vis[i+1][j]=vis[i][j]=false;}if(j+1<n&&!vis[i][j+1]){vis[i][j+1]=vis[i][j]=true;dfs(s+2);vis[i][j+1]=vis[i][j]=false;}return;}} }int main() { // freopen("input.txt","r",stdin);while(scanf("%d",&n)!=EOF){memset(vis,false,sizeof(vis));ans=0;dfs(0);cout<<n<<": "<<ans<<endl; }return 0; }

可以得到的數據：1 5 11 36 95 281 781 2245 6336 18061 51205 145601

第二步：通過for循環尋找系數：?

?

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e4+200;int a[]={1,5,11,36,95,281,781,2245,6336,18061,51205,145601};int main() { // freopen("input.txt","r",stdin);for(int a1=-20;a1<=20;a1++)for(int a2=-20;a2<=20;a2++)for(int a3=-20;a3<=20;a3++)for(int a4=-20;a4<=20;a4++)for(int a5=-20;a5<=20;a5++)for(int a6=-20;a6<=20;a6++)for(int i=0;i+6<12;i++)if(a1*a[i]+a2*a[i+1]+a3*a[i+2]+a4*a[i+3]+a5*a[i+4]+a6*a[i+5]==a[i+6])if(i==5&&a1==0)cout<<a6<<' '<<a5<<' '<<a4<<' '<<a3<<' '<<a2<<' '<<a1<<endl;return 0; }

找到末尾0的個數較多的一項，在本題中即1 5 1 -1 0，故遞推公式為dp[i]=dp[i-1]+5*dp[i-2]+dp[i-3]-dp[i-4]

第三步：矩陣快速冪模板?

上代碼之前有個小細節要注意，就是矩陣中涉及到了負數，而負數直接運算取模會出現異常錯誤，所以為了避免此類錯誤，我們在取模的時候要稍微處理一下，可以有兩種方法：

先取模再運算

先運算再取模

我這里用的是先運算再取模，上代碼：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> #include<cmath> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=4;//a[i]=a[i-1]+5*a[i-2]+a[i-3]-a[i-4]const LL mod=1000000007;struct M {LL a[N][N]; };M operator*(M a,M b) {M temp;memset(temp.a,0,sizeof(temp.a));for(LL i=0;i<N;i++)for(LL j=0;j<N;j++){temp.a[i][j]=0;for(LL k=0;k<N;k++){temp.a[i][j]=(temp.a[i][j]+(a.a[i][k]*b.a[k][j]+mod)%mod)%mod;}}return temp; } M q_pow(M a,LL n) {M ans;memset(ans.a,0,sizeof(ans.a));for(LL i=0;i<N;i++)ans.a[i][i]=1;while(n){if(n&1)ans=ans*a;a=a*a;n>>=1;}return ans; }int main() { // freopen("input.txt","r",stdin);LL n;while(scanf("%lld",&n)!=EOF){if(n==1){cout<<1<<endl;continue;}else if(n==2){cout<<5<<endl;continue;}else if(n==3){cout<<11<<endl;continue;}else if(n==4){cout<<36<<endl;continue;}M start;memset(start.a,0,sizeof(start.a));start.a[0][0]=start.a[0][1]=start.a[1][2]=start.a[2][3]=start.a[2][0]=1;start.a[1][0]=5;start.a[3][0]=-1;M ans;memset(ans.a,0,sizeof(ans.a));ans.a[0][0]=36;ans.a[0][1]=11;ans.a[0][2]=5;ans.a[0][3]=1;M res=q_pow(start,n-4);cout<<(ans*res).a[0][0]<<endl; /* M temp=q_pow(start,2);temp=ans*temp;for(int i=0;i<N;i++){for(int j=0;j<N;j++)cout<<temp.a[i][j]<<' ';cout<<endl;}*/}return 0; }

杜教BM：

#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <string> #include <map> #include <set> #include <cassert> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef vector<int> VI; typedef long long ll; typedef pair<int,int> PII; const ll mod=1000000007; ll powmod(ll a,ll b) {ll res=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res; } int _,n; namespace linear_seq {const int N=10010;ll res[N],base[N],_c[N],_md[N];vector<int> Md;void mul(ll *a,ll *b,int k) {for(int i = 0 ; i < k + k ; ++i)_c[i]=0;for(int i = 0 ; i < k ;++i)if (a[i])for(int j = 0 ;j < k ;++ j)_c[i+j]=(_c[i+j]+a[i]*b[j])%mod;for (int i=k+k-1;i>=k;i--)if (_c[i])for(int j = 0 ; j<(int ) Md.size() ; ++ j)_c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod;for(int i =0 ; i< k ; ++i)a[i]=_c[i];}int solve(ll n,VI a,VI b) {ll ans=0,pnt=0;int k=SZ(a);assert( SZ(a) == SZ(b) );for(int i = 0 ;i < k ; ++ i)_md[k-1-i] = -a[i] ; _md[k] = 1 ;Md.clear() ;for(int i =0 ; i < k ; ++ i)if (_md[i]!=0)Md.push_back(i);for(int i = 0; i< k ;++ i)res[i]=base[i]=0;res[0]=1;while ((1ll<<pnt)<=n)pnt++;for (int p=pnt;p>=0;p--) {mul(res,res,k);if ((n>>p)&1) {for (int i=k-1;i>=0;i--) res[i+1]=res[i];res[0]=0;for(int j = 0 ;j < (int)Md.size() ; ++ j)res[ Md[j] ]=(res[ Md[j] ]-res[k]*_md[Md[j]])%mod;}}rep(i,0,k) ans=(ans+res[i]*b[i])%mod;if (ans<0) ans+=mod;return ans;}VI BM(VI s) {VI C(1,1),B(1,1);int L=0,m=1,b=1;for(int n= 0 ;n < (int)s.size(); ++ n ) {ll d=0;for(int i =0 ; i < L +1 ;++ i)d=(d+(ll)C[i]*s[n-i])%mod;if (d==0) ++m;else if (2*L<=n) {VI T=C;ll c=mod-d*powmod(b,mod-2)%mod;while (SZ(C)<SZ(B)+m)C.push_back(0);for(int i =0 ; i < (int)B.size(); ++ i)C[i+m]=(C[i+m]+c*B[i])%mod;L=n+1-L; B=T; b=d; m=1;} else {ll c=mod-d*powmod(b,mod-2)%mod;while (SZ(C)<SZ(B)+m)C.push_back(0);for(int i = 0 ;i <(int) B.size() ; ++ i)C[i+m]=(C[i+m]+c*B[i])%mod;++m;}}return C;}ll gao(VI a,ll n) {VI c=BM(a);c.erase(c.begin());for( int i = 0 ; i < (int)c.size( );++i )c[i]=(mod-c[i])%mod;return (ll)solve(n,c,VI(a.begin(),a.begin()+SZ(c)));} }; int main() {long long n;VI a;int N,v;a.push_back(1);a.push_back(5);a.push_back(11);a.push_back(36);a.push_back(95);a.push_back(281);a.push_back(781);a.push_back(2245);a.push_back(6336);a.push_back(18061);a.push_back(51205); for (;~scanf("%lld",&n);)printf("%lld\n",linear_seq::gao(a,n-1));return 0 ; }

?

總結

以上是生活随笔為你收集整理的HDU - 6185 Covering(暴搜+递推+矩阵快速幂/杜教BM)的全部內容，希望文章能夠幫你解決所遇到的問題。

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