小城镇建设网站的观点,汽车app网站建设,网站建设北京个人,手机网站怎么开发工具正题 题目大意
求121\times 212的方块铺满4n4\times n4n的方格方案总数。 解题思路
首先 当计算fnf_nfn时#xff0c; 显然最后一排可以(−−−−)(∣∣∣∣)(−−∣∣)(∣−−∣)(∣∣−−)(--\ --)(|\ \ |\ \ |\ \ |)(--\ \ |\ \ |)(|\ \ --\ \ |)(|\ \ |--)(−− −−)…正题 题目大意
求1×21\times 21×2的方块铺满4×n4\times n4×n的方格方案总数。 解题思路
首先 当计算fnf_nfn时 显然最后一排可以(−−−−)(∣∣∣∣)(−−∣∣)(∣−−∣)(∣∣−−)(--\ --)(|\ \ |\ \ |\ \ |)(--\ \ |\ \ |)(|\ \ --\ \ |)(|\ \ |--)(−− −−)(∣ ∣ ∣ ∣)(−− ∣ ∣)(∣ −− ∣)(∣ ∣−−)
然后第一种显然方案数是fn−1f_{n-1}fn−1 第二种显然是fn−2f_{n-2}fn−2 主要是后三种是一样的: (∣∣−−)(|\ \ |--)(∣ ∣−−)或(∣∣∣∣)(|\ \ |\ \ |\ \ |)(∣ ∣ ∣ ∣) (∣∣−−)(|\ \ |--)(∣ ∣−−)或(∣∣−−)(|\ \ |--)(∣ ∣−−) 继续往后推会发现其实最后答案∑i1n−2fi\sum_{i1}^{n-2} f_{i}∑i1n−2fi
那么答案就变成了4∗fn−2fn−3−fn−44*f_{n-2}f_{n-3}-f_{n-4}4∗fn−2fn−3−fn−4 然后和前面两种加起来就是fnfn−15∗fn−2fn−3−fn−4f_{n}f_{n-1}5*f_{n-2}f_{n-3}-f_{n-4}fnfn−15∗fn−2fn−3−fn−4
矩阵乘法加速即可 codecodecode
#includecstdio
#includecstring
#define ll long long
using namespace std;
const ll SIZE4;
ll n,m;
struct matrix{ll a[SIZE][SIZE];
}f;
matrix operator *(matrix a, matrix b) {matrix c;memset(c.a,0,sizeof(c.a));for (ll i0;iSIZE;i)for (ll j0;jSIZE;j)for (ll k0;kSIZE;k)(c.a[i][j]a.a[i][k]*b.a[k][j])%m;return c;
}
void ycl()
{memset(f.a,0,sizeof(f.a));f.a[3][3]1;f.a[3][2]1;f.a[2][3]5;f.a[1][3]1;f.a[0][3]-1;f.a[2][1]1;f.a[1][0]1;
}
matrix power(matrix f,ll b)
{matrix ans;memset(ans.a,0,sizeof(ans.a));ans.a[0][3]ans.a[0][1]ans.a[0][0]1;while(b){if(b1) ansans*f;ff*f;b1;}return ans;
}
int main()
{while(1){scanf(%lld%lld,n,m);if(!n!m) return 0;ycl();fpower(f,n);//for(ll i0;iSIZE;i)// printf(%lld ,f.a[0][i]);printf(%lld\n,(f.a[0][3]m)%m);}
}
