hdu 6185 Covering

2019-04-14 19:52发布

站内文章 / 模拟电子
12966 0 1629
题目链接 看到题就想起以前做过的类似多米诺骨牌相关的题目，想着应该是有递推式的，菜鸟的我就开始画图，画到废了废了，之后借助网上大佬博客的递推演算：   行数为4 当n=2时，方案数为5； 当n>2时，方案数可由5种情况组合： 第一种情况(第一列填充满)： num1=f[n-1]； 第二种情况(前两列填充满)： num2=f[n-2]; 第三种情况(根据列填充满判断)： num3=f[n-2]+f[n-3]+……+f[0]; 第四种情况同第三种： num4=num3; 第五种情况判断方法同第三种： num5=f[n-2]+f[n-4]+……+f[0]/f[1]; 所以：f[n]=num1+num2+num[3]+num[4]+num[5]; 因为第五种中存在两种情况，为了避免，采取f[n]-f[n-2]，整理可得： f[n]=f[n-1]+5f[n-2]+f[n-3]-f[n-4]; 再利用矩阵快速模幂求解，注意负数模幂先加上mod 1≤n≤10181 /*矩阵快速幂*/ #include #include #include using namespace std; typedef long long ll; const ll mod=1e9+7; const int N=4; struct Matrix{//矩阵结构体 ll a[16][16]; void init(){ //初始化为单位矩阵 memset(a,0,sizeof(a)); for(int i=0;i>=1; t=matrix(t,t); } } int main() { ll n; while(~scanf("%lld",&n)) { if(n==1) printf("1 "); else if(n==2) printf("5 "); else if(n==3) printf("11 "); else if(n==4) printf("36 "); else { memset(g.a,0,sizeof(g.a)); g.a[0][0]=1; g.a[0][1]=5; g.a[0][2]=1; g.a[0][3]=-1; g.a[1][0]=1; g.a[2][1]=1; g.a[3][2]=1; qpow(n-4); printf("%lld ",(ans.a[0][0]*36l%mod+ans.a[0][1]*11l%mod+ans.a[0][2]*5l%mod+ans.a[0][3])%mod); } } return 0; } 可以借助暴力搜索得出前几个数据再进行找规律（这个提交会TL） #include #include #include #include #include using namespace std; typedef long long ll; const int mod = 1e9 + 7; int mp[15][15]; int vis[15][15]; int n; ll sum=0; int cnt=0; bool safe(int x, int y) { //是否越界 if (x>=0&&x<4&&y>=0&&y  

热门文章